---

---

迪杰斯特拉（Dijkstra）算法是一个按路径长度递增的次序产生最短路径的算法，要求所有边的权重都为非负值。

算法思路

下图为一无向网图：

如果以A为源点，求A至各顶点的最短路径。

（1）先将A到各点的最短距离赋值为A与各点的边权值，A到A的最短路径为0，我们将已找到最短路径的顶点集合称为集合M，未找到最短路径的顶点集合称为集合N。如图（1）所示。

（2）寻找离A点最近的顶点，显然是C顶点，此时A->C的最短路径长度必定是4，将C顶点纳入集合M中。

以C顶点为中心，其相邻的集合N中的顶点B、D、E，它们经过C顶点到A顶点的距离分别为7、13、6，将这个路径的距离与各点原本的距离比较，如果经过C顶点的路径距离更短，那么修改最短路径长度。如图（2）所示。

（3）寻找A到集合N中距离最短的顶点，显然是E顶点，将其纳入到集合M中。

以E顶点为中心，其相邻的集合N中的顶点D，到E的距离5，因为经过E到A的路径$6+5=11$小于原本的最小路径距离13，所以修改其最短路径，如图（3）所示。

（4）寻找A到集合N中距离最短的顶点，显然是B顶点，将其纳入到集合M中。

以B顶点为中心，其相邻的集合N中的顶点D，到B的距离1，因为经过E到A的路径$7+1=8$小于原本的最小路径11，所以修改其最短路径，如图（4）所示。

（5）寻找A到集合N中距离最短的顶点，显然是D顶点，将其纳入到集合M中，此时图的全部顶点均已找到最短路径。如图（5）所示。

---

---

算法程序

程序比较简单，主要分为以下几部分：

（1）final[MAXVEX]用于表示各顶点是否已经找到最短路径了，14-22行是参数的初始化。

（2）26-34行是寻找源点A到集合N中距离最短的顶点，即下一个路径最短的顶点。

（3）38-46行是修正集合N中各顶点的最短路径，经过已找到最短路径的顶点到源点，也许会更短。

两个嵌套for循环可以得到此算法的时间复杂度为$O(n^2)$。

typedef int Pathmatirx[MAXVEX]; //各顶点的最短路径的前驱顶点数组
typedef int ShortPathTable[MAXVEX]; //各顶点的最短路径数组
/*********************************************************************\
*function: 按照路径长度递增的次序产生最短路径
*intput: MGraph G - 图的邻接矩阵； int v0 - 起始点
*output:(*p)[v] - 前驱顶点下标；(*D)[v] - v0到v的最短路径
*return: void
\*********************************************************************/
void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatirx *P, ShortPathTable *D)
{
    int v, w, k, min;
    int final[MAXVEX]; //finial[w] = 1表示求得顶点v0至vw的最短路径

    for (v = 0; v < G.numVertexes; v++)
    {
        final[v]  = 0; //全部顶点初始化为未知最短路径状态
        (*D)[v] = G.arc[v0][v]; //将与v0点有连线的顶点加上权值
        (*P)[v] = 0; //初始化路径数组P为0
    }

    (*D)[v0] = 0; //v0至v0的路径为0
    final[v0] = 1; //v0至v0不需要求路径

    for (v = 1; v < G.numVertexes; v++)
    {
        min = INFINITY; //最短距离初始化为∞
        for (w = 0; w < G.numVertexes; w++) //寻找离v0最近的顶点
        {
            if (!final[w] && (*D)[w] < min)
            {
                k = w;
                min = (*D)[w];
            }
        }

        final[k] = 1; //将目前找到的最短路径的顶点置为1

        for (w = 0; w < G.numVertexes; w++) //修正当前最短路径及距离
        {
            /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
            if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
            {
                (*D)[w] = min + G.arc[k][w]; //修改当前路径长度
                (*P)[w] = k;
            }
        }
    }
}

#include "CreateGraph.h"
#include "Dijkstra.h"
int main()
{

    MGraph G;
    int v0 = 0;
    int j = 0;
    Pathmatirx P;
    ShortPathTable D;
    CreateMgraph(&G);
    ShortestPath_Dijkstra(G, v0, &P, &D);
    for (int i = 0; i < G.numVertexes; i++)
    {
        printf("最短路径：%c", G.vexs[i]);
        j = i;
        do
        {
            j = P[j];
            printf (" -- %c", G.vexs[j]);
        }while (j != v0);
        printf("   长度：%d \n", D[i]);

    }
    return 0;
}

打印输出如下：

---

---

Dijkstra算法的正确性

此算法使用的是贪心策略，虽然贪心策略并一定能获得最优结果，但此算法可以通过贪心策略计算出最短路径，因为

定理：Dijkstra算法运行在带权重的图G=（V, E)时，如果所有权值均为非负值，则在算法终止时，对于所有结点$u\in V$，我们有$u.d=\delta (s,u)$。

推论：如果在带有权重的图G=(V, E)上运行Dijkstra算法，其中的权重均为非负值，源点为s，则在算法终止时，前驱子图$G_{\pi }$是一颗根结点为s的最短路径树。

证明可参考《算法导论》