头衔：ENDLESS
等级：版主
文章：36
积分：116
注册：2004-11-24 |
 弗洛伊德算法
弗洛伊德算法
弗洛伊德算法仍从图的带权邻接矩阵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的最短路径。按此方法，可以同时求得各对顶点间的最短路径。
问题：求任意两点间的最短路径。
①②③④⑤⑥1223441789
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
|
|
|
|
注册
趣题之家 → 信息学竞赛 → 算法艺术 → 弗洛伊德算法
2005-03-15 23:08
