《算法技术手册》单源最短路径

假设你有一架私人飞机，你需要寻找一条从Saint Johnsbury到Waco的最短路径。你知道所有城市的机场之间的距离，并且它们之间都是相互可达，不需要途中停留。解决这个问题的最广为人知的算法是Dijkstra算法（图6-13）。找到最短路径之后，这个搜索可能会终止。如果近似的结果可以接受，那么我们能够根据启发式的信息来引导搜索，这就是这个算法的一个变种（A*搜索，在第7章讨论）。

本质上，Dijkstra算法贪婪地扩展顶点集S，对于S中的每一个顶点v来说，s到v的最短路径已经计算出来。计算v的最短路径时，我们使用S中顶点的路径。S最开始为{s}。算法如图6-14所示对S扩展，Dijkstra算法寻找到距离源点s距离最短的顶点v(v∈V-S)，然后顺着v的边看看是否存在一条最短路径到达另外一个顶点。在处理v2之后，算法通过路＜s，v2，v3＞计算出s到v3的最短路径是17。一旦S扩展到等于V时，算法完成。

输入/输出

输入

一个有向有权图G=(V,E)以及一个源点s∈V。图中每一条边e=(u,v)都有一个相关的正权值。n是图G中的顶点数。

输出

Dijkstra算法得到两个数组。主要的计算结果是数组dist，其值表示s到图中每个顶点的距离。注意dist[s]等于0。次要的计算结果是数组pred，这个数组能够用来构造从源点s到图中每个顶点的最短路径。你需要重新审视一下例6-3，看看pred是如何更新的。

假设

边的权值是正数，如果这个假设不是真的，那么dist[u]的值有可能会是无效的。更坏的是，如果图中存在一个负值环，Dijkstra算法可能会陷入死循环。在图6-13的第12行中，我们假设不会有算术溢出，你必须注意，简单地添加一个对newLen≥0的检查。