迭代算法(ford算法) Dijkstra 算法只能适合权为正值的情况,但当权为负值时,是Dijkstra 算法爱莫能助,这时只要图中不存在负权回路可用迭代算法。 迭代算法的思想:不停地调整图中的顶点值(源点到该点的最短路径值),直到没有点的值调整了为止。 程序如下: programzudlouj;
const n=6;max=10000 ;
cost:array[1..6,1..6] ofreal=((0,50,10,max,45,max),(max,0
,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),(
max,max,max,30,0,max),(max,max,max,3,max,0));
var dist:array[1..n] of real;
path,p:array[1..n] of 1..n;
first,tail,u:1..n;
s:set of 1..n;
i,j,y,m:integer;
min:real;
quit:boolean;
begin
read(first,tail);
for i:=1 to n do dist:=max;
dist[first]:=0;
repeat
quit:=true;
for i:=1 to n do
if dist<max then
for j:=1 to n do
if dist+cost[i,j]<dist[j] then
begin
dist[j]:=dist+cost[i,j];
path[j]:=i;
quit:=false;
end;
until quit;
writeln('mindist(',first,',',tail,')=',dist[tail]:8:2);
y:=tail;m:=0;
while (y<>first) do
begin inc(m);p[m]:=y;y:=path[y]; end;
write('path:',first);
for j:=m downto 1 do
write('->',p[j]);
writeln;
end.
2. 2 一点到其它所有点的最短路径
例2:如下图:求起点到所有点的最短路径?
1.下面是Dijkstra 算法: 基本思想是:设置一个顶点的集合s,并不断地扩充这个集合,一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点,并且调整非s中点的最短路径长度,找当前最短路径点,将其加入到集合s中,直到所有的点都在s中。 programzudlouj;
const n=6;max=10000 ;
cost:array[1..6,1..6] ofreal=((0,50,10,max,45,max),(max,0
,15,max,10,max),(20,max,0,15,max,max),(max,20,max,0,35,max),(
max,max,max,30,0,max),(max,max,max,3,max,0));
var dist:array[1..n] of real;
path,p:array[1..n] of 1..n;
first,u:1..n;
s:set of 1..n;
i,j,y,m:integer;
min:real;
begin
read(first);
for i:=1 to n do dist:=max;
dist[first]:=0;
s:=[first]; u:=first;
for i:=1 to n-1 do
begin
for j:= 1 to n do
if not(j in s) and (dist+cost[u,j]<dist[j]) then
begin dist[j]:=dist+cost[u,j];path[j]:=u end;
min:=max;
for j:=1 to n do
if not(j in s) and (dist[j]<min) then beginu:=j;min:=dist[j];end;
s:=s+;
end;
for i:=1 to n do
if i<>first then
if dist<>max then
begin
writeln('mindist(',first,',',i,')=',dist:8:2);
y:=i;m:=0;
while (y<>first) do
begin inc(m);p[m]:=y;y:=path[y] end;
write('path:',first);
for j:=m downto 1 do
write('->',p[j]);
writeln;
end
else
writeln('mindist(',first,',',i,'):','No answer');
end.
|