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 :

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:

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