算法原理

Dijkstra算是一个按路径长度递增的次序产生最短路径的算法。简单来理解，有两个主要的步骤：

1. 比较：当前（这个可能会在下一步更新）各个点到源点的距离，拥有最短距离的点（假设为v2）的当前路径即v2到源点的最短路径
2. 更新：对于没有求出最短路径的点，如果通过上一步求出的最短路径+彼此连接的弧长度小于当前该点到源点的距离，则将新的路径作为该点的最短路径
   重复1、2操作，直到求出所有点的最短路径。

算法实例

问题：给定带权有向图G和源点v0，求v到G中其余各顶点的最短路径

以上这张表就是求解的整个过程：
其中，vj：当前循环求出vj到源点的最短距离
S：已经求出最短路径的集合
1. 第一次循环
竖着看表格
v1和v0没有路径，距离为无限大;
v0和v2的弧长为10，距离为10;
同理， v3为无限大，v4为30，v5为100

这5个点到源点距离最短的是v2，那v2的最短路径就求出来了，路径就是v0直接到v2

2. 第二次循环
剩余v1,v3,v4,v5没有求出来
因为新求出最短路径的v2到v1没有弧连接，因此，v0-v2这条最短路径对于v1没有影响，不更新
v3到v0的距离本来为无限大，有了v0-v2的路径之后，v0-v2-v3的距离和为60，比原来短，更新v3的路径
同理，v2到v4没有路径（也可以看成是无限大），不更新；到v5没有路径，不更新

现在，v1,v3,v4,v5中路径最短的是v4，那v4到v0的最短路径就求出来，就是v0-v4

3. 第三次循环
剩余v1,v3,v5没有求出来
v4到v1没有连接弧，不更新，依然为无限大
v0-v4-v3的路径总长度为50，比之前的60短，更新v3的当前最短路径为v0-v4-v3，长度为50
v0-v4-v5的路径总长度为90，比之前的100短，更新v5的当前最短路径为v0-v4-v5，长度为90

现在，v1,v3,v5中路径最短的是v3，那v3到v0的最短路径就求出来，是v0-v4-v3

4. 第四次循环
剩余v1,v5没有求出来
v3到v1没有连接弧，不更新，依然为无限大
v0-v4-v3-v5的路径总长度为60，比之前的90短，更新v5的当前最短路径为v0-v4-v3-v5，长度为60

现在，v1,v5中路径最短的是v5,那v0到v5的最短路径就是v0-v4-v3-v5

5. 第五次循环
剩余v1没有求出来，v5到v1没有路径，不更新。那v0到v1的最短路径就是没有路径

C语言描述的Dijkstra算法

看到这里，你懂了吗？想当初大二学习的时候就是因为这个算法被老师表扬了一番，可开心了。