空间分析算法( 三 ) _生活百科

文章插图
S, Vi

文章插图
V} , Vj就是当前求得的一条从V出发的最短路径的终点。令S=S U { j}(标记j) 。(3) 修改从出发到集合V-S上所有顶点Vk可达的最短路径长度。如果Dist[j]+Cost[j, k]<Dist[k]则修改Dist [k]为:(也称为鬆弛操作)Dist[k]=Dist[j]+Cost[j，k] 。(4) 重複操作(2) , (3)共N-1次。由此求得从V到图上其余各顶点的最短路径是依路径长度递增的序列。弗洛伊德算法弗洛伊德算法能够求得每一对顶点之间的最短路径，其基本思想是：假设从顶点Vi到Vj的最短路径。若从Vi到Vj有弧，则从Vi到Vj存在一条长度为COST [ i, j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(Vi, V1, Vj)是否存在(即判别弧(Vi, V1)和弧(V1, Vj)是否存在) 。如果存在，则比较(Vi, Vj)和(Vi, V1, Vj)的路径长度，较短者为从Vi到Vj的中点顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点V2，也就是说，若(Vi，…，V2)和(V2，...，Vj)分别是当前找到的中间顶点的序号不大于1的最短路径，那幺(Vi，...，V2，...，Vj)就有可能是从Vi到Vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从Vi 到Vj的中间顶点的序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V3，继续进行试探。依次类推，在经过n次比较之后，最后求得的必是从Vi 到Vj的最短路径。按此方法，可同时求得各对顶点间的最短路径。算法共需3层循环，总的时间複杂度是O(

文章插图
)。