在网图和非网图中，最短路径的含义是不同的。网图是两顶点经过的边上权值之和最少的路径。非网图是两顶点之间经过的边数最少的路径。
我们把路径起始的第一个顶点称为源点，最后一个顶点称为终点。
image.png

1.迪杰斯特拉算法原理

  1. #define MAXVEX    9
  2. #define    INFINITY    65535
  4. typedef    int    Patharc[MAXVEX];            // 用于存储最短路径下标的数组
  5. typedef int    ShortPathTable[MAXVEX];        // 用于存储到各点最短路径的权值和
  7. void ShortestPath_Dijkstar(MGraph G, int V0, Patharc *P, ShortPathTable *D)
  8. {
  9.     int v, w, k, min;
  10.     int final[MAXVEX];        // final[w] = 1 表示已经求得顶点V0到Vw的最短路径
  12.     // 初始化数据
  13.     for( v=0; v < G.numVertexes; v++ )
  14.     {
  15.         final[v] = 0;                // 全部顶点初始化为未找到最短路径
  16.         (*D)[V] = G.arc[V0][v];        // 将与V0点有连线的顶点加上权值
  17.         (*P)[V] = 0;                // 初始化路径a数组P为0
  18.     }
  19.     (*D)[V0] = 0;        // V0至V0的路径为0
  20.     final[V0] = 1;        // V0至V0不需要求路径
  22.     // 开始主循环，每次求得V0到某个V顶点的最短路径
  23.     for( v=1; v < G.numVertexes; v++ )
  24.     {
  25.         min = INFINITY;
  26.         for( w=0; w < G.numVertexes; w++ )
  27.         {
  28.             if( !final[w] && (*D)[w]<min )
  29.             {
  30.                 k = w;
  31.                 min = (*D)[w];
  32.             }
  33.         }
  34.         final[k] = 1;    // 将目前找到的最近的顶点置1
  36.         // 修正当前最短路径及距离
  37.         for( w=0; w < G.numVextexes; w++ )
  38.         {
  39.             // 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
  40.             if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )
  41.             {
  42.                 (*D)[w] = min + G.arc[k][w];    // 修改当前路径长度
  43.                 (*p)[w] = k;                    // 存放前驱顶点
  44.             }
  45.         }
  46.     }
  47. }

2.弗洛伊德算法

  1. #define MAXVEX    9
  2. #define INFINITY    65535
  4. typedef int Pathmatirx[MAXVEX][MAXVEX];
  5. typedef int ShortPathTable[MAXVEX][MAXVEX];
  7. void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
  8. {
  9.     int v, w, k;
  11.     // 初始化D和P
  12.     for( v=0; v < G.numVertexes; v++ )
  13.     {
  14.         for( w=0; w < G.numVertexes; w++ )
  15.         {
  16.             (*D)[v][w] = G.matirx[v][w];
  17.             (*P)[v][w] = w;
  18.         }
  19.     }
  21.     // 优美的弗洛伊德算法
  22.     for( k=0; k < G.numVertexes; k++ )
  23.     {
  24.         for( v=0; v < G.numVertexes; v++ )
  25.         {
  26.             for( w=0; w < G.numVertexes; w++ )
  27.             {
  28.                 if( (*D)[v][w] > (*D)[v][k] + (*D)[k][w] )
  29.                 {
  30.                     (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
  31.                     (*P)[v][w] = (*P)[v][k];        // 请思考：这里换成(*P)[k][w]可以吗？为什么？
  32.                 }
  33.             }
  34.         }
  35.     }
  36. }