HỌC TIN CÙNG THỦ KHOA

Mời các bạn Download code tại: Click here

1. File Input:

- Dòng đầu tiên gồm 3 số n, s, t tương ứng là số đỉnh, đỉnh bắt đầu và đỉnh kết thúc để tìm đường đi ngắn nhất từ s tới t.

- n dòng tiếp theo, mỗi dòng gồm n số là ma trận trọng số của đồ thị, trong đó quy ước a[i, j] = 0 nếu không có đường đi trực tiếp từ i tới j.

2. File Output

- Ghi ra độ dài đường đi ngắn nhất từ s tới t.

- Hiển thị đường đi ngắn nhất từ s tới t.

Bài viết liên quan: Hai phương pháp chứng minh thuật toán Dijkstra - Tìm đường đi ngắn nhất trên đồ thị

const fi = 'DIJKSTRA.INP';
      fo = 'DIJKSTRA.OUT';
      MAXN = 1000;
      oo = MAXINT div 2;
var n, s, t: integer;
    a: array [1..MAXN, 1..MAXN] of integer;
    L, Truoc: array [1..MAXN] of integer;
    { Truoc[i] luu dinh ngay truoc i trong duong di ngan nhat
     tu s toi i }
    cx: array [1..MAXN] of boolean;
    f: text;

    procedure Nhap;
    var i, j: integer;
    begin
        assign(f, fi); reset(f);
        readln(f, n, s, t);
        for i:= 1 to n do
                for j:= 1 to n do
                        read(f, a[i, j]);
        close(f);
    end;

    procedure Dijkstra;
    var u, i, minL: integer;
    begin
        for i:= 1 to n do L[i]:= +oo;
        L[s]:= 0;
        fillchar(cx, sizeof(cx), true);
        for i:= 1 to n do Truoc[i]:= -1;
        repeat // Lap lai cong viec sau
                minL:= +oo;
                // Tim ra dinh chua duoc co dinh nhan va
                // co nhan be nhat de co dinh nhan
                for i:= 1 to n do
                        if cx[i] = true then
                                if minL > L[i] then
                                begin
                                        minL:= L[i];
                                        u:= i;
                                end;
                cx[u]:= false; // Co dinh nhan cho dinh u
                // Sau khi u duoc co dinh nhan thi do dai duong di ngan nhat
                // tu s toi u la L[i]

                // Cap nhat lai nhan cho nhung dinh chua duoc
                // co dinh nhan

                for i:= 1 to n do
                        if cx[i] = true then
                                if a[u, i] > 0 then
                                      if L[i] > L[u] + a[u, i] then
                                      begin
                                        L[i]:= L[u] + a[u, i];
                                        Truoc[i]:= u;
                                      end;

        until u = t;
    end;

    procedure Duyet(i: integer);
    begin
        if Truoc[i] = -1 then write(f, i)
                else begin
                        Duyet(Truoc[i]);
                        write(f, ' -> ', i);
                     end;
    end;

    procedure InKQ;
    begin
        assign(f, fo); rewrite(f);
        writeln(f, L[t]);
        Duyet(t);
        close(f);
    end;

BEGIN
        Nhap;
        Dijkstra;
        InKQ;
END.