专注细节
努力进步

图之最短距离

最短路径

1,从一个结点到其余各结点的最短路径

a,狄克斯特拉算法

算法原理:设置两个结点的集合S和T,集合S中存放已经找到的最短路径的结点,集合T中存放当前还未找到的最短路径的结点。初始情况时,集合S中只含有源点,设为V0,然后不断从集合T中选择到源点V0到集合T中生育结点的当前最短路径长度值,集合T中各结点的新的当前最短路径长度值,为原来的最短路径长度值与从源点过结点u到达该结点的路径长度中的较小者

代码见狄克斯特拉算法

2,每对结点之间的最短路径

很明显,像之前的狄克斯特拉也可以解决每对结点之间的最短路径问题,只需要每次以不同的结点作为源点使用狄克斯特拉算法计算从该源点到其余结点的最短路径。这样,重复调用n次即可以求出每对结点之间的最短路径,由于狄克斯特拉算法的时间复杂度为O(n^2),所以这种算法的时间复杂度为O(n^3).

而弗洛伊德提出一种解决图中每对结点之间的最短路径的算法:

B,弗洛伊德算法

算法原理:设矩阵cost用来存放带权有向图G的权值,即矩阵元素cost[i][j]存放着序号为i的结点到序号为j的结点之间的权值,可以通过递推构造一个矩阵序列A0,A1,A2,…,AN来求每对节点之间的最短路径。其中,Ak[i][j](0=<k=<n)表示从结点vi到结点vj的路径上所经过的结点序号不大于k的最短路径长度。初始时,A0[i][j]=cost[i][j]。

假定已经求出Ak,递推求解Ak+1,则显然分为两种情况考虑:一种情况是该路径不经过结点序号为k+1的结点,此时该路径长度与从结点vi到结点vj的所经过结点序号不大于k的最短路径长度相同;另一种情况是经过结点序号为k+1的结点,此时路径分为两段,一段是从结点vi到结点vk+1的最短距离,另一端是从结点vk+1到结点vj的最短路径,此时路径长度等于这两段最短路径长度之和。而这两种情况中路径长度较小者,就是要求的从结点vi到结点vj的路径上所经过的结点序号不大于k+1的最短路径长度。经过n次递推后得到的An[i][j]就是考虑了经过途中所有结点情况下从几点vi到结点vj的最短路径长度。

代码见弗洛伊德算法

另外有个博友写了一个相关博文,我做成了pdf文档,写的很不错:Floyd.pdf

分享到:更多 ()