Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng Pascal

Về thuật toán Dijkstra có 2 loại

• Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới 1 đỉnh đích
• Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới các đỉnh còn lại của đồ thị.

– Dùng 1 mảng Len[] – Len[i] là khoảng cách ngắn nhất từ đỉnh a tới đỉnh i.

– Dùng 1 mảng S đánh dấu các đỉnh i đặc biệt (các đỉnh i mà thời điểm hiện tại thì đường đi từ a tới i là ngắn nhất).

– Dùng mảng P[] đánh dấu đường đi. P[j] = i nếu i là đỉnh đi trước j trong đường đi ngắn nhất.

– Đặt lại giá trị vô cùng cho các cặp đỉnh không có đường đi.

– Khởi tạo tất cả các đường đi từ a đên các đỉnh khác bằng vô cùng.

– Khởi tạo đường đi từ a đến chính a = 0.

– Duyệt hết các đỉnh V của đồ thị

• Tìm đỉnh i chưa nằm trong S mà đường đi từ a tới i là ngắn nhất để đưa vào S. Nếu không tìm được đỉnh nào nghĩa là đã duyệt hết các đỉnh có thể đi mà vẫn chưa thấy đỉnh đích => không thể đi được.
• Nếu tìm được đỉnh i thì duyệt tất cả các đỉnh j chưa nằm trong S. Nếu Len[i] + G[i][j] < Len[j] (trong đó G[i][j] là khoảng cách từ đỉnh i tới đỉnh j) thì gán Len[j] = Len[i] + G[i][j]; và đánh dấu đường đi P[j] = i.

Lưu ý: Do trong C, mảng bắt đầu từ 0. Do vậy các đỉnh khi tính toán thì sẽ tính từ đỉnh 0 đến đỉnh n-1. Tuy nhiên khi hiển thị ra thì vẫn phải là từ đỉnh 1 đến n và trong file input.inp thì đỉnh đầu và đỉnh cuối cũng sẽ được tính từ 1 đến n. Do đó trong code trước khi tính toán ta cần giảm đỉnh đầu và đỉnh cuối đi 1 đơn vị. Sau khi tính toán xong thì khi xuất kết quả lại cần tăng các đỉnh trong đường đi tìm được lên 1 đơn vị để hiển thị đúng (VD ta muốn tính đường đi từ đỉnh 4 đến đỉnh 8, thì đỉnh 4 tương ứng với vị trí thứ 3 trong mảng, đỉnh 8 ứng với vị trí thứ 7 nên ta cần giảm 4 xuống 3, 8 xuống 7 để tính toán. Khi tìm được đường đi, giả sử là 3 -> 5 -> 4 -> 7 thì phải in ra là 4 -> 6 -> 5 -> 8).

Chúng ta sẽ đi thực hành với đồ thị sau theo 2 code là làm ngay trong main và thực hiện theo các hàm:

file input.inp: hàng đầu tiên thể hiện có 8 điểm, đi từ điểm 4 đến điểm 8. ma trận 8×8 ở dưới là ma trận kề của đồ thị.

Cài đặt bằng Pascal

const INP = 'input.txt';
var
        f : text;
        n, i, j, a, b, sum : integer;
        len, s, p : array[1..1000] of integer;
        G : array[1..100,1..100] of integer;
BEGIN

        {doc du lieu tu tep}
        assign(f, INP);
        reset(f);

        readln(f, n, a, b);
        writeln(n, ' ', a, ' ', b);
        sum :=0;
        for i:=1 to n do
        begin
                for j:=1 to n do
                begin
                        read(f, G[i, j]);
                        sum := sum + G[i, j];
                end;
                readln(f);
        end;

        {dat vo cung cho tat ca cap dinh khong co duong di}
        for i:=1 to n do
                for j:=1 to n do
                        if (i <> j) and (G[i, j] = 0) then
                                G[i, j] := sum;

        for i:=1 to n do
        begin
                len[i] := sum; {khoi tao do dai tu a toi moi dinh la vo cung}
                s[i] := 0;     {danh sach cac diem da xet}
                p[i] := a;     {diem bat dau cua moi dinh la a}
        end;                   {do dai tu a den a la 0}
        len[a] := 0;

        while (s[b] = 0) do     {trong khi dinh b chua duoc duyet}
        begin
                for i:=1 to n do    {tim 1 dinh chua xet ma co the di tu a den no}
                begin
                        if (s[i]=0) and (len[i] < sum) then
                        begin
                                break;
                        end;
                end;
                if i>n then      {khong tim thay dinh nao, dung lai}
                begin
                        break;
                end;

                for j:=1 to n do     {tim dinh ma duong di tu a den no la nho nhat}
                        if (s[j] = 0) and (len[i] > len[j]) then i := j;

                s[i] := 1;            {danh dau da duyet}

                for j:=0 to n do      {tinh lai duong di den cac dinh chua xet}
                        if (s[j] = 0) and (len[i] + G[i, j] < len[j]) then
                        begin
                                len[j] := len[i] + G[i, j];
                                p[j] := i;
                        end;
        end;

        i := b;
        while(i <>a) do
        begin
                write(i, ' <-- ');
                i := p[i];
        end;
        writeln(a);
END.