|
|
|
|
|
|
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的最短路径，算法结束。
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
