对于网图来说，最短路径是指两顶点间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

迪杰斯特拉(Dijkstra)算法

mark

思路：按路径长度递增的次序产生最短路径，从某一个顶点开始，寻找与当前整体距离最近的顶点，依次找下去，直到到达终点。

代码：

#define MAXVEX 9
#define INFINITY 65535
typedef int Pathmatirx[MAXVEX];//用于存储最短路径下标数组
typedef int ShortPathTable[MAXVEX];//用于存储到当前整体到其余各点最短路径的权值和

void ShortestPath_Dijkstra (MGraph G,int v0,Pathmatirx *P,ShortPathTable *D)
{
    int min,k;
    int final[MAXVEX];//final[w]=1表示求得顶点v0至vw的最短路径
    for (int v = 0;v < G.numVertexes;v++)
    {
        final[v] = 0;//全部顶点初始化为未知路径状态
        (*D)[v] = G.arc[v0][v];//用当前整体v0到各个顶点的边的权值初始化数组D
        (*P)[v] = 0;//初始化路径数组为0
    }
    (*D)[v0] = 0;//v0到v0的路径为0(这句话似乎可以省略???)
    final[v0] = 1;//v0到v0不需要求路径
    for (int v = 1;v < G.numVertexes;v++)
    {
        min = INFINITY;
        for (int w = 0;w < G.numVertexes;w++)
        {
            if (!final[w] && (*D)[w] < min)
            {
                k = w;//更新为最小权值所在边另一个顶点的下标
                min = (*D)[w];//更新为离当前整体的最小权值
            }
        }
        //该循环用于寻找离当前整体最近的顶点
        final[k] = 1;//将目前找到的最近的顶点置为1
        for (int w = 0;w < G.numVertexes;w++)
        {
            if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
            {
            //说明找到了更短的路径，修改两数组
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
        }//该循环用于取新整体与原整体到其余顶点的边的权值的最小值来更新数组D
        //或者说通过新顶点搭桥产生的路径变化
    }
}

理解上注意：该算法并不会刻意寻找到某个顶点的最短路径，因此不能按照一笔画的思路来理解该算法。

final数组最终为:{1,1,1,1,1,1,1,1,1}，它表示所有顶点均完成了最短路径的查找工作。

D数组最终为:{0,1,4,7,5,8,10,12,16}，它表示v0到各个顶点的最短路径数，如v0到v8的最短距离为16。

P数组最终为:{0,0,1,4,2,4,3,6,7}，它表示最短路径所经过的顶点，P[8]=7的意思是v8的前驱顶点是v7，如v0到v8经过的路径为v8←v7←v6←v3←v4←v2←v1←v0。

可以得到v0到任意一个顶点的最短路径和路径长度，如v0到v8的最短路径中，没有v5，但D[5]=8表示v0到v5的最短路径长度为8，由P数组可得v0到v5经过的最短路径为v5←v4←v2←v1←v0。

时间复杂度为O(n²)，若求所有顶点到所有顶点的最短路径则执行n次，时间复杂度为O(n³)。

弗洛伊德(Floyd)算法

mark

原理：
$$
D^0[v][w] = min {D^(-1) [v][w] , D^(-1)[v][0] + D^(-1)[0][w]}
$$
D^0、P^0表示初始数组，D^(-1)、P^(-1)表示经过v1搭桥处理后的数组，依次类推。

即：任意寻找一个顶点，判断以该顶点为桥任意两个顶点之间的距离是否会缩短。

代码：

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
//因为求的是所有顶点到所有顶点的最短路径，所以是二维数组
void ShortestPath_Floyd (MGraph G,Pathmatirx *P,ShortPathTable *D)
//P[v][w]存储最短路径，D[v][w]存储带权长度
{
    for (int v = 0;v < G.numVertexes;v++)
    {
        for (int w = 0;w < G.numVertexes;w++)
        {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w;
        }
    }//初始化操作
    
    for (int k = 0;k < G.numVertexes;k++)//k表示中转顶点
    {
        for (int v = 0;v < G.numVertexes;v++)//v表示起始顶点
        {
            for (int w = 0;w < G.numVertexes;w++)//w表示结束顶点
            {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
                {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];//路径设置为经过下标为k的顶点
                }
            }
        }
    }
}

最终结果为：

mark

不难发现，v0所在的列与Dijkstra算法结果完全一致。

如求v4到v7的最短路径，P[4]/[7]=3，P[3]/[7]=6，P[6]/[7]=7，故路径为v4→v3→v6→v7。(markdown中两个方括号表示链接，为了区分我在中间加了/表示二维数组。)

求最短路径的显示代码：

for (int v = 0;v < G.numVertexes;v++)
{
    for (int w = v+1;w < G.numVertexes;w++)
    {
        printf("v%d-v%d weight: %d ",v,w,(*D)[v][w]);
        k = P[v][w];//获得第一个路径顶点下标
        printf("path: %d",v);//打印源点
        while (k != w)
        {
            printf(" -> %d",k);//打印路径顶点
            k = P[k][w];//获得下一个路径顶点下标
        }
        printf(" -> %d\n",w);//打印终点
    }
    printf("\n");
}

时间复杂度为O(n³)，面临需要求所有顶点到所有顶点的最短路径时比较方便。