单源最短路径

百度百科

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。

问题描述

给定一个带权有向图 G=(V,E)。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

Dijkstra算法的解决方案

即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

Dijkstra算法的解题思想

• 1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径

  • 创建一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行
  • 设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。

• 2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。

• 3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。

  • 调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。
    即算法当中得

    if(min + g.edges[v][k] < d[k])
    {
        d[k] = min + g.edges[v][k];
    }
    

• 4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

举个书上的题当作例子

123

初始化的距离向量

• 选A作为源点，A到各顶点的距离即为距离向量

这时候的路径向量为：

• 只有与A有点关联的结点才有路径向量为0,其他均为 -1

123

接下来，就是将源点A到其他结点距离最短的结点找出来，这里最短的是到D结点加到集合S当中,并且：

• 由于D的加入，导致A到F的距离由∞变为33 + 15 = 48
• A到G的距由40变为A->D->G = 15 + 23 = 38
• D的下标为3,所以v变为3

距离向量变为：

由于现在A到G和F通过了D顶点，导致顶点G和F的前驱结点变为了D，即路径向量变为3

路径向量为：

123

接下来继续向后找，发现最短的路径是到E,所以将其加入集合S，并且：

• A到C的距离由∞变为了A->E->C = 28 + 33 = 61
• 其他的均未变化

距离向量变为：

由于A->C变成了A->E->C,所以C的前驱结点变为了E，即4

路径向量为：

继续向下推导，最终结果为：

距离向量：

路径向量：

可以从表中的数据得出：

• 由于B的路径向量为0,即A,所以A->B的最短路径就是A->B
• C的路径向量为5，即F,而F的路径向量为3，即D,D的路径向量为0,是A,所以A到C的最短路径即为 A->D->F->C

总结为：

代码：

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define M 30  /*预定义图的最大顶点数*/
#define FINITY 5000  //用 5000代替无穷


//最小生成树算法的结构体
typedef struct {
    char vexs[M];  //顶点的数据域
    int edges[M][M];  //定义的邻接矩阵
    int n, e;  //图中的顶点数和边数
}Mgraph;


typedef struct edgedata
{
    int beg, en;  //beg,en都是顶点序号
    int length;  //边长
}edge;



void create(Mgraph *g, char *filename, int c)  //c = 0表示创建无向图 
{
    int weight = 0;  //边的权值
    int front, rear; //变得前驱和后驱
    FILE *file;
    file = fopen(filename, "r"); //从文件读取图的边信息
    if (file)
    {
        fscanf(file, "%d%d\n", &g->n, &g->e);  //读取图的顶点数与边数
        for (int i = 0; i < g->n; i++)
        {
            fscanf(file, "%c", &g->vexs[i]);  //读取图中顶点的信息域
        }
        for (int i = 0; i < g->n; i++)
        {
            for (int j = 0; j < g->n; j++)
            {
                if (i == j)
                    g->edges[i][j] = 0;  //对角线上的均为0
                else
                    g->edges[i][j] = FINITY;  //没有赋值的域均加成无
            }
        }
        for (int k = 0; k < g->e; k++)
        {
            fscanf(file, "%d%d%d", &front, &rear, &weight);
            g->edges[front][rear] = weight;  //只些相应顺序的，即有向图
            if (c == 0)
                g->edges[rear][front] = weight;  //对称图形，即为无向图
        }
        fclose(file);
    }
    else
    {
        g->n = 0;
        printf("文件打开失败！\n");
    }
}


// 图的最短路径
 typedef enum{FALSE,TRUE} boolean;  /*FALSE 为0，TRUE为1*/
 typedef int dist[M];  //距离向量类型
 typedef int path[M];  //路径类型

 /*
 Dijkstra算法求单源最短路径
 g 有向图
 root 根节点
 p 路径   p[i] 用于保存最短路径上第i个顶点的前驱顶点的序号
 d 距离向量  用于保存从源点出发的顶点到其他顶点的距离向量
 */
 void Dijkstra(Mgraph g,int root,path p, dist d)
 {
     int v = 0;  //用于临时保存
     int min = 0;
     boolean final[M];  //表示当前元素是否已经求出最短路径，定义为布尔类型
     for (int i = 0; i < g.n; i++)  //初始化各种集合与距离向量
     {
         final[i] = FALSE;  //全部赋值为FALSE
         d[i] = g.edges[root][i];
         if (d[i] < FINITY && d[i] != 0)  //非自我路径和达不到的路径  
             p[i] = root;  //前驱结点为根结点
         else
             p[i] = -1;  //当前结点无前驱结点
     }
     final[root] = TRUE; //初始时s只有一个根节点root一个结点
     d[root] = 0;
     printf("%d到其他顶点的最短距离为：\n", root);
     for (int i = 1; i < g.n; i++)
     {
          min = FINITY;
          for (int k = 0; k < g.n; ++k)  //循环找出最小边入结点
          {
              if (!final[k] && d[k] < min)  //如果还没有求出最短路径并且存在更短的路径
              {
                  v = k;  //将初始结点替换为当前结点
                  min = d[k]; //min保存最短路径
              }
          }
          
          printf("\n%d-->%d 路径长度： %d\n",root,g.vexs[v], min);
          if (min == FINITY)  //如果得出的路径无法达到
              return;
          final[v] = TRUE; //该结点已经求出最短路径
          //修改S到V-S中各结点的距离
          for (int i = 0; i < g.n; ++i)
             if (!final[i] && (min + g.edges[v][i] < d[i]))
             {
                  d[i] = min + g.edges[v][i]; //最短路径等于之前的最短路径加上最近的最短路径
                  p[i] = v;  //将 路径向量赋值
             }
     }
 }

 void print_dpd(Mgraph g, path p, dist d)
 {
     int st[M], pre, top = -1;//定义栈st并初始化空栈
     printf("\n\n最短路径为：\n\n");
     for (int  i = 0; i < g.n; i++)
     {
         printf("路径长度：%3d  ", d[i]); //将距离向量输出
         st[++top] = i; //将i入栈
         pre = p[i];  //储存当前
         while (pre != -1)
         {
             st[++top] = pre;  //让pre入栈
             pre = p[pre];
         }
         printf("路径走向：");
         while (top > 0)
             printf("%2d", st[top--]);
         printf("\n");
     }
 }


int main()
{
    Mgraph g;
    char filename[20] = "D:\\Desktop\\Test.txt";
    path p; //路径向量
    dist d;  //最短路径向量
    int root;
    create(&g, filename, 1);
    printf("请输入源点：\n");
    scanf("%d", &root);
    Dijkstra(g, root, p, d);
    print_dpd(g, p, d);
    system("pause");
    return 0;
}

文件格式

image.png

输出结果：

image.png