|
网上贸易 创造奇迹! 阿里巴巴 Alibaba Powered By Dvbbs Version 7.1.0 Copyright ©2003 - 2006 QTHome.Org 页面执行时间 00.17188 秒, 2 次数据查询 |
 |
| 以文本方式查看主题 - 趣题之家 (http://qthome.org/bbs/index.asp) -- 算法艺术 (http://qthome.org/bbs/list.asp?boardid=38) ---- 弗洛伊德算法 (http://qthome.org/bbs/dispbbs.asp?boardid=38&id=291) |
| -- 作者：remlostime -- 发布时间：3/15/2005 11:08:20 PM -- 弗洛伊德算法 弗洛伊德算法 弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是： 假设求从顶点vi到vj的最短路径，如果从vi到vj有弧，则从vi到vj存在一条长度为的路径，该路径下一定是最短路径，尚需进行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的最短路径。按此方法，可以同时求得各对顶点间的最短路径。
问题：求任意两点间的最短路径。 ① ② ③ ④ ⑤ ⑥ 1 2 2 3 4 4 1 7 8 9
program Floyd; const max=6; 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)); of integer; P:路径数组 start,ending,i,j,k:integer; START:始点, ENDING:终点 procedure print(i,j:integer); 递归输出I到J的最短路径 var k:integer; begin ; if k<>0 then begin print(i,k);write(k,\'=>\');print(k,j);end; end; begin write(\'start,ending:\'); readln(start,ending); :=0; 路径变量清零 for k:=1 to max do 对V进行max次替换 for i:=1 to max do for j:=1 to max do then 若I经过K到J比I直接到J费用低则替换 :=k;end; =0表示I直接到J write(start,\'=>\');print(start,ending);writeln(ending); end.
p:任意两点路径 如何输出任意两点间路径： =5知5为中间点 =2知2为（1，5）中间点 =0知1至2，2至5为直达 =4知4为（5，6）中间点，而（5，4），（4，6）无中 2 0 0 0 0 4 得路径为1→2→5→4→6 间点 5 5 4 0 4 0
|
|
|||