Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất

CÀI ĐẶT THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI NGẮN NHẤT BẰNG CHƯƠNG TRÌNH PASCAL
Thuật toán Dijkstra.
Chương trình thuật toán tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z.
Dữ liệu được lấy từ tệp DIJKSTRA.INP có cấu trúc :

n
(số đỉnh)
m
(số cạnh)
a
(đỉnh đầu)
z
(đỉnh cuối)

Đỉnh đầu
Đỉnh cuối
Trọng số


x1
y1
w1


x2
y2
w2


…
…
…


xm
ym
wm



Sau khi lấy dữ liệu, chương trình sẽ xác định có tồn tại đường đi ngắn nhất, tìm đường đi ngắn nhất đó và lưu vào tệp DIJKSTRA.OUT có cấu trúc:

Dòng đầu : “NO” nếu không tồn tại

Dòng đầu : “YES” nếu tồn tại

 Dòng 2: L(z) độ dài đường đi ngắn nhất

 Dòng 3: a--> z1-->z2-->…zn-->z là đường đi ngắn nhất



Chương trình: (DIJKSTRA.PAS)

PROGRAM thuat_toan_Dijkstra;
Uses crt;
Const
max=100;
oo=32000;
Type
mang=array[1..max] of integer;
Var
a:array[1..max,1..max] of integer;
d:mang;
truoc:mang;
chon:array[1..max] of boolean;
n,m,s,z:integer;
u,v,i:integer;
f,g:text;

Procedure input;
begin
writeln(`doc du lieu tu file Dijkstra.inp`);
assign(f,`Dijkstra.inp`);reset(f);
readln(f,n,m,s,z);
for u:=1 to n do
for v:=1 to n do
if u=v then a[u,v]:=0 else a[u,v]:=oo;
for i:=1 to m do readln(f,u,v,a[u,v]);
close(f);
end;
Procedure Init;
Begin
for v:=1 to n do
begin
d[v]:=a[s,v];
truoc[v]:=s;
chon[v]:=false;
end;
d[s]:=0;
chon[s]:=true;
u:=s;
End;
Procedure Dijkstra;
Var
min:integer;
Begin
Repeat
for v:=1 to z do
if (not chon[v]) and (d[v] > d[u]+a[u,v]) then
begin
d[v]:= d[u] + a[u,v];
truoc[v]:=u;
end;
min:=oo;
for i:=1 to n do
if (not chon[i]) and (d[i]< min) then
begin
min:=d[i];
u:=i;
end;
if (min<> oo) then chon[u]:=true;
Until (chon[z]) or (min=oo);
End;
Procedure Output;
Var st,tam:string;
Begin
writeln(`ghi ket qua ra file dijkstra.out`);
assign(g,`dijkstra.out`);rewrite(g);
if d[z]=oo then
writeln(`NO`)
else
begin
writeln(g,`YES`);
writeln(g,d[z]);
st:=``;
while (z<>s) do
begin
str(z,tam);
st:=st+tam;
z:=truoc[z];
end;
write(g,s);
for i:=length(st) downto 1 do write(g,` -> `,st[i]);

end;
close(g);
end;
BEGIN
clrscr;
input;
init;
dijkstra;
output;
readln;
END.
File vào ví dụ: (DIJKSTRA.INP)
4 7 1 4
1 2 7
1 3 5
2 4 6
2 3 7
3 4 11
4 1 4
4 2 1
File ra tương ứng: (DIJKSTRA.OUT)
YES
13
1 -> 2 -> 4