最短路径

最短路径

　

问题描述：file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image001.jpg

如图：求v1到v10的最短路径长度及最短路径。

　

图的邻接矩阵如下：

0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 13 12 11 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0

采用逆推法

设f（x）表示点x到v10的最短路径长度

则 f(10)=0

  f(x)=min{ f(i)+a[x,i] 当a[x,i]>0,x<i<=n}

程序如下：（逆推法）

program lt3;
const n=10;
var
a:array[1..n,1..n] of integer;
b,c:array[1..n] of integer;
fname:string;
f:text;
i,j,x:integer;
begin
readln(fname);
assign(f,fname);
reset(f);
for i:=1 to n do
  for j:=1 to n do
   read(f,a[i,j]);
close(f);
for i:=1 to n do
  b:=maxint;
b[n]:=0;
for i:= n-1 downto 1 do
  for j:=n downto i+1 do
   if (a[i,j]>0) and (b[j]<>maxint) and(b[j]+a[i,j]<b)
    then begin b:=b[j]+a[i,j];c:=j end;
writeln('minlong=',b[1]);
x:=1;
  while x<>0 do
   begin
   write(x:5);
   x:=c[x];
  end;
end.