|
|
Dijkstra(迪杰斯拉特)算法和Floyd(弗洛伊德)算法为求给定带权有向图G的最短路径的两种方法,其中Dijkstra算法用于求图中某一顶点到其余顶点的最短路径,Floyd算法用于求图中每一对顶点之间的最短路径。
|
|
|
Dijkstra算法提出了一个按路径递增的顺序产生最短路径的算法。首先引入一个辅助向量D,它的分量D(i)表示当前所有找到的从始点V到每个终点Vi的最短路径的长度。其初态为:若从V到Vi有弧,则D(i)为弧上权,否则为无穷大;显然,长度为D(j)=Min{D(i)|Vi∈V}的路径是从V出发的一条最短路径,此路径为(V, Vj)。下一条次短的路径可通过下面的算法求得:设次短路径的终点是Vk,则这条路径或者是(V, Vk),或者是(V, Vj, Vk)。其长度或者是从V到Vk的弧上的权值,或者是D(j)和从Vj到Vk的弧上的权值之和。
|
|
|
Dijkstra算法的时间复杂度为O(n2)。但对于n个顶点的图,求每一对顶点间的最短路径,若按Dijkstra算法,求每一个顶点到其他各顶点间的最短路径,即在上面的基础上,再加一层循环,时间复杂度是O(n3)。而Floyd算法,虽然时间复杂度也是O(n3),但形式上简单。
|
|
|
Floyd算法的思想是:设求顶点Vi到Vj间的最短路径,若Vi到Vj有弧,则弧上的权值是一条路径,但未必是最短路径,要经过n-1次测试。首先将顶点V1加入,即看(Vi, V1),(V1, Vj)是否有路径,且比(Vi, Vj)低,如果是,则用后两段路径代替,并称这是Vi到Vj中间顶点序号不大于1的最短路径。再将顶点V2加入,得到Vi到Vj中间顶点序号不大于2的最短路径。如此下去,直到Vn加入,得到Vi到Vj中间顶点序号不大于n的最短路径,算法结束。
|
|
|
|
|
|
|
|
|
|
|
|