{本程序解决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;