数据结构与算法_最短路径

    给定有向带权图G = ( V, E ),其中每条边的权是非负实数。此外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其他顶点的最短路径长度，这里路径长度指路上各边的权之和。

    如何求源点到其他各顶点的最短路径呢？

Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[ ]。一旦S包含了所有的顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。

算法步骤：

1）数据结构。设置地图的带权邻接矩阵为G.Edge[ ][ ],即如果从源点u 到顶点 i 有边，就令 G.Edge[ u ][ i ]等于<u,i>的权值，否则G.Edge[ u ][ i ] = 无穷大（写程序时用一个大数表示例如Ox7fffffff）；采用一维数组dist[ i ]来记录从源点到 i 顶点的最短路径长度；采用一维数组p[ i ]来记录最短路径上 i 顶点的前驱。

2）初始化。令集合S = { u }，对于集合V-S中的所有顶点x,初始化 dist[ i ] = G.Edge[ u ][ i ]，如果源点u到顶点i有边相连，初始化p[ i ] = u,否则p[ i ] = -1。

3) 找最小。在集合V-S中依照贪心策略来寻找时的dist[ j ]具有最小值的顶点 t,即dist[ t ] = min(dist[j] | j属于V-S集合)，则顶点 t  就是集合V-S中距离源点u 最近的顶点。

4）加入S战队。将顶点 t 加入集合S中，同时更新V-S。

5）判结束。如何集合 V-S 为空，算法结束，否则转 6）。

6） 借东风。 在 3） 中已经找到了源点到 t 的最短路径，那么集合V-S 中所有与顶点 t相邻的顶点 j,都可以借助 t 走捷径。如果 dist[ j ] > dist[ t ]+G.Edge[t] [j],则dist[j] = dist[t] +G.Edge[t] [j] ,记录顶点j 的前驱为t，有p[j] = t ,转 3）。 

一个例子：

1）数据结构

设置地图的带权邻接矩阵为G.Edge[] []，即如果从顶点i 到顶点 j 有边，则G.Edge[ i ] [ j ]等于

< i, j >的权值，否则 G.Edge[ i ] [ j ] = 无穷大，如图所示：

2) 初始化

令集合S = { 1 }, V-S = {2,3,4,5},对于集合V-S中的所有顶点 x , 初始化最短距离数组 dist[ i ] = G.Edge[1][i],dist[ u ] = 0;如果源点1 到顶点 i 有边相连，初始化前驱数组 p[i] = 1,否则 p[i] = -1。

3） 找最小

在集合V-S = {2, 3, 4, 5}中，依照贪心策略来寻找 V-S 集合中dist[ ]最小的顶点t。

4）加入S战队

将顶点 t  = 2加入集合S中S = {1,2},同时更新 V-S ={3 ,4 ,5 },如图所示：

5）借东风

刚刚找到了源点到 t = 2的最短路径，那么对集合V-S中所有t 的邻接点 j,都可以借助t 走捷径，我们从图或邻接矩阵都可以看出，2号结点的邻接点是 3和 4 号结点。

6）找最小

在集合 V-S = { 3, 4, 5}中，依照贪心策略来寻找dist[ ]具有最小值的顶点 t ，依照贪心策略来寻找 V-S 集合中 dist[ ]最小的顶点t：

7） 加入S战队

将顶点  t = 3加入集合S中 S = { 1, 2, 3},同时更新 V-S = {4, 5],如图所示：

8） 借东风

刚刚找到源点到 t = 3的最短路径，那么对集合V-S中所有 t的邻接点j,都可以借助 t 走捷径。我们从图中或者邻接矩阵可以看出，3号结点的邻接矩阵是4和5号结点。

先看4号结点能否借助3号走捷径： dist[ 3 ] + G.Edge[3][4] = 4+7 = 11，而当前 dist[ 4 ] = 8 < 11，比当前路径还长，因此不更新。

再看5号结点能否借助3号走捷径：dist[3] + G.Edge[3][5] = 4+1 = 5,而当前 dist[5] = 无穷大 > 5。因此可以走捷径即 3 -> 5,更新 dist[5] 5,记录顶点 5的前驱为 3，即p[5] = 3。

9）找最小

在集合 V-S = {4, 5}中，依照贪心策略来寻找V-S集合中dist[ ]最小的顶点t。

10） 加入S战队

将顶点 t = 5 加入集合S中 S = {1, 2, 3, 5],同时更新V-S = { 4 },如图所示：

11） 借东风

刚刚找到了源点到 t = 5的最短路径，那么集合 V-S 中所有t 的邻接点j,都可以借助 t 走捷径。我们从图或邻接矩阵可以看出，5号结点没有邻接点，因此不更新。

12） 找最小

在集合 V-S = { 4 }中，依照贪心策略来寻找 dist[ ]最小的顶点 t，只有一个顶点，所以很容易找到，如图所示：

13）加入S战队

将顶点 t 加入集合S中，S = {1, 2, 3, 5, 4],同时更新V-S = { }。