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ố
x
1
y
1
w
1
x
2
y
2
w

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;

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