单对顶点间的最短路径

单对顶点间的最短路径

例1：输入起点，终点，求其最短路径？

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,tail,u:1..n;
    s:set of 1..n;
    i,j,y,m:integer;
    min:real;
begin
read(first,tail);
for i:=1 to n do dist:=max;
dist[first]:=0;
s:=[first]; u:=first;
while u<>tail 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;
   if min=max then begin writeln('No answer');halt end;
   s:=s+;
  end;
  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.