shortestroadsearch.txt

求解最短路径的各种算法

最短路径 
A.标号法求解单源点最短路径： 
var 
a:array[1..maxn,1..maxn] of integer; 
b:array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径} 
mark:array[1..maxn] of boolean; 

procedure bhf; 
var 
best,best_j:integer; 
begin 
fillchar(mark,sizeof(mark),false); 
mark[1]:=true; b[1]:=0;{1为源点} 
repeat 
best:=0; 
for i:=1 to n do 
If mark[i] then {对每一个已计算出最短路径的点} 
for j:=1 to n do 
if (not mark[j]) and (a[i,j] >0) then 
if (best=0) or (b[i]+a[i,j]< best) then begin 
best:=b[i]+a[i,j]; best_j:=j; 
end; 
if best >0 then begin 
b[best_j]:=best；mark[best_j]:=true; 
end; 
until best=0; 
end;{bhf} 

B.Floyed算法求解所有顶点对之间的最短路径： 
procedure floyed; 
begin 
for I:=1 to n do 
for j:=1 to n do 
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点} 
for k:=1 to n do {枚举中间结点} 
for i:=1 to n do 
for j:=1 to n do 
if a[i,k]+a[j,k]< a[i,j] then begin 
a[i,j]:=a[i,k]+a[k,j]; 
p[I,j]:=p[k,j]; 
end; 
end; 

C. Dijkstra 算法： 
类似标号法，本质为贪心算法。 
var 
a:array[1..maxn,1..maxn] of integer; 
b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点} 
mark:array[1..maxn] of boolean; 
procedure dijkstra(v0:integer); 
begin 
fillchar(mark,sizeof(mark),false); 
for i:=1 to n do begin 
d[i]:=a[v0,i]; 
if d[i]< >0 then pre[i]:=v0 else pre[i]:=0; 
end; 
mark[v0]:=true; 
repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} 
min:=maxint; u:=0; {u记录离1集合最近的结点} 
for i:=1 to n do 
if (not mark[i]) and (d[i]< min) then begin 
u:=i; min:=d[i]; 
end; 
if u< >0 then begin 
mark[u]:=true; 
for i:=1 to n do 
if (not mark[i]) and (a[u,i]+d[u]< d[i]) then begin 
d[i]:=a[u,i]+d[u]; 
pre[i]:=u; 
end; 
end; 
until u=0; 
end;