数据结构与算法13

迪杰斯特拉算法

迪杰斯特拉算法是一种典型的贪心算法，用于在一个图中求取从某结点出发到其它每一个结点的最短路径。这里的最短路径不是指路径长度的最短，而是所带有的边上权重之和最小。这个算法的核心原理是这样的：如果有结点s,t,r，并且我们已经找到了s→t的最短路径和t→r的最短路径，那么这两条邻接一合并就是s→r的最短路径。

就像这幅插图，这里面的箭头指的不是边而是指三条不同的路径。这里有s,r,t三个结点，三条路径具备各自长度l_a,l_b,l_c。图中的结点s可以用路径a以l_a的距离到达结点t，也可以先经过路径b去结点r再通过路径c抵达结点t。那么后者就有l_b+l_c的距离。如果l_a<l_b+l_c则最短路径肯定不是先走b再走c的这一条，也许是直接走a的那条最短，也许不是；而反过来要是l_a>l_b+l_c的话，那直接走a肯定不是最短的，但先b后c的路径也不一定是最短的。不过一旦我们引入这样一个前提：

如果从s到t不能经过r，则此时允许的最短的路径是a
如果从s到t一定需要经过r，则此时允许的最短的路径是先b后c

这时我们能发现一个有趣的事实：从s到t要么经过r要么不经过，所以整体而言这两条路径必然有一条是最短路径，我们只要比较大小，看看l_a与_b+l_c取那个小的就是答案。

但如何确保此种前提条件成立呢？若是,t,r都邻接，那么请问这两条路径哪一个相对更短呢？只需比较l_a与_b即可。因为一旦l_a<_b的话，光是b就比a长了再走上c的距离肯定更远是不行的。反之则不一定，还得参考l_c。因此对于一个起点s，若有结点t与之邻接，我们可以另一个同样与s邻接的结点r，看s直接到t是不是比s先去r再到t更近，如果是，那么s→t的最短路径就是直达，否则，我们就要在后面考虑有没有更短的。

算法过程如下：

准备工作
首先，确定算法的起点是一个结点s，到自身距离为0
设立结点集合P表示尚未查出最短路径的结点集合，T表示已经查出的最短路径的结点集合。
除了起点s在T中外，其它所有结点都放在P中。
与s邻接的结点，已知最短距离为和s之间的边的权重。剩下的结点，已知最短距离皆为∞

开启循环：
从P中选取已知最短距离相对而言最小的那个，暂名为t
认定s→t的路径最短只能是这么短，无法再短。移t入T
遍历P中剩余所有结点
对这其中的每一个结点，暂名为r
取【s→r的已知最短距离】,与【(s→t的最短路径距离)+(t→r一步到位的距离)】，比较大小
如果【(s→t的最短路径距离)+(t→r一步到位的距离)】更小，用其替代【s→r的已知最短距离】在P中
第二层循环结束
如果P空，T满，则第一层循环结束

观T，其中记载了s到图中每一个结点的最短路径

看例子，研究结点A到其它所有结点的最短路径有多短。

轮次	P	T	当前发现最短路径
1	B2直达 C4直达 D5直达 E∞不通 F∞不通 G∞不通	B2	B2，直达
2	C3自B D5直达 E9自B F8自B G∞不通	B2 C3	C3，自B
3	D5直达 E9自B F8自B G5自C	B2 C3 D5	D5，直达
4	E8自D F8自B G5自C	B2 C3 D5 G5	G5，自C
5	E8自D F8自B	B2 C3 D5 G5 E8	E8，自D
6	F8自B	B2 C3 D5 G5 E8	F8，自B

这个过程表格中，每一步我们都要把每一个结点中当前已知的最短的路径下，要走的是一个结点是什么记下来。当然，已知的最短的路径有多短也要记下来。这样做的目的在于，在最后可以反向构造出最优解。我们不仅能知道A到每一个结点的最短路径有多短，还能知道怎么走才能这么短。

最优解内容如下：
到B，直达，距离2
到C，路径ABC，距离3
到D，直达，距离5
到E，路径ADE，距离8
到F，路径ABF，距离8
到G，路径ABCG，距离5

该算法是有适用范围的，不是所有图均可，条件如下： ①没有多重边，要不然你得先把多重边合并，权值取最小的那个；②没有环，要不然算法会转来转去无穷无尽； ③权重大于等于0，否则在负权值的干扰下算法同样会转来转去没完没了

数学和计算机科学板块_辛酸网

数据结构与算法13