弗洛伊德算法
弗洛伊德算法仍从图的带权邻接矩阵cost 出发,其基本思想是:
假设求从顶点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,也就是说,如果(v1 ,...,v2,)和(v2 ,...,v1)分别是当前找到的中间顶点的序号不大于1的最短路径,那么(v1 ,... v2, ,...vj )就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点诒不大于1的最短路径相比较,从中选出间顶点的序号不大于2的最短路径之后,再增加一个顶点v3,继续进行试探。依次类推,在一般情况下,若(vi ,...,vk)和(vk,...,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径,则将(vi ,... vk,...vj )和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较,其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样,在经过n次比较后,最后求得的必是从vi到vj的最短路径。按此方法,可以同时求得各对顶点间的最短路径。
问题:求任意两点间的最短路径。
program Floyd;
const max=6;
v:array[1..max,1..max] of integer=(( 0, 4, 8,99,99,99),
( 4, 0, 3, 4, 1,99),
( 8, 3, 0, 2, 2,99),
(99, 4, 2, 0, 1, 7),
(99, 1, 2, 1, 0, 9),
(99,99,99, 7, 9, 0));
var p:array[1..max,1..max] of integer; P:路径数组
start,ending,i,j,k:integer; START:始点, ENDING:终点
procedure print(i,j:integer); 递归输出I到J的最短路径
弗洛伊德算法仍从图的带权邻接矩阵cost 出发,其基本思想是:
假设求从顶点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,也就是说,如果(v1 ,...,v2,)和(v2 ,...,v1)分别是当前找到的中间顶点的序号不大于1的最短路径,那么(v1 ,... v2, ,...vj )就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点诒不大于1的最短路径相比较,从中选出间顶点的序号不大于2的最短路径之后,再增加一个顶点v3,继续进行试探。依次类推,在一般情况下,若(vi ,...,vk)和(vk,...,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径,则将(vi ,... vk,...vj )和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较,其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样,在经过n次比较后,最后求得的必是从vi到vj的最短路径。按此方法,可以同时求得各对顶点间的最短路径。
问题:求任意两点间的最短路径。
program Floyd;
const max=6;
v:array[1..max,1..max] of integer=(( 0, 4, 8,99,99,99),
( 4, 0, 3, 4, 1,99),
( 8, 3, 0, 2, 2,99),
(99, 4, 2, 0, 1, 7),
(99, 1, 2, 1, 0, 9),
(99,99,99, 7, 9, 0));
var p:array[1..max,1..max] of integer; P:路径数组
start,ending,i,j,k:integer; START:始点, ENDING:终点
procedure print(i,j:integer); 递归输出I到J的最短路径