一霎微雨洒庭轩

2007-08-22

Dijkstra最短路径(一点到各顶点最短路径) - [Algorithms]

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://conoon.blogbus.com/logs/7858419.html

{本程序解决6个顶点之间的最短路径问题,各顶点间关系的数据文件在sj.txt中}
{如果顶点I到顶点J不能直达就设置距离为30000}
program dijkstra;
type
   jihe=set of 0..5;
var
   a:array[0..5,0..5] of integer;
   dist:array[0..5] of integer;
   i,j,k,m,n:integer;
   fv:text;
   s:jihe;
begin
   s:=[0];
   assign(fv,'sj.txt');
   reset(fv);
   for i:=0 to 5 do  {从文件中读数据,其中a[i,j]代表从顶点i到顶点j的直达距离,如果不通用30000代替}
     begin
        for j:=0 to 5 do read(fv,a[i,j]);
        readln(fv)
     end;
   for i:=1 to 5 do  {设置DIST数组的初始值,即为顶点0到各顶点的直达距离(算法的第一步)}
      dist[i]:=a[0,i];
   for i:=1 to 5 do
   begin
        m:=0;
        dist[m]:=30000;    {设置DIST[M]的目的是为下面的一步做准备,即在DIST数组中一个最小的值}

        for j:=1 to 5 do    {算法的第二步,找最小的DIST值}
        if (not (j in s)) and (dist[m]>dist[j]) 
         then m:=j ;    {用M来记录到底是哪个顶点}
        s:=s+[m];    {把顶点加入S中}

        for k:=1 to 5 do     {算法的第三步,修改后面的DIST值}
           if (not (k in s)) and  (dist[k]>dist[m]+a[m,k])
             then
               dist[k]:=dist[m]+a[m,k]
   end;
   writeln('原各顶点间的路径关系是：（30000代表不通）');
   for i:=0 to 5 do
      begin
        for j:=0 to 5 do  write(a[i,j]:6);
        writeln
      end;
   writeln; writeln;