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 L[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.

Program ThuatToanFloyd;
// Tim duong di ngan nhat giua tat ca cac cap dinh cua do thi
const fi = 'FLOYD.INP';
      fo = 'FLOYD.OUT';
      MAXN = 1000;
      oo = MAXINT div 2;
var f: text;
    n, s, t: integer;
    L, Truoc: array [1..MAXN, 1..MAXN] of integer;

    procedure Nhap;
    var i, j: integer;
    begin
        assign(f, fi); reset(f);
        readln(f, n, s, t);
        // Cach xay dung do thi
        for i:= 1 to n do
                for j:= 1 to n do
                begin
                        read(f, L[i, j]);
                        if L[i, j] = 0 then
                                if i <> j then
                                        L[i, j]:= +oo; // Khac voi Dijkstra
                        Truoc[i, j]:= -1;
                end;
        close(f);
    end;

    procedure Floyd;
    var i, j, k: integer;
    begin
        for k:= 1 to n do
                for i:= 1 to n do
                        for j:= 1 to n do
                                if L[i, j] > L[i, k] + L[k, j] then
                                begin
                                        L[i, j]:= L[i, k] + L[k, j];
                                        Truoc[i, j]:= k;
                                end;

    end;


    procedure TruyVet(i, j: integer);
    // Tim duong di ngan nhat tu i toi j
    var k: integer;
    begin
        if Truoc[i, j] = -1 then write(f, i, ' -> ')
                else
                begin
                        k:= Truoc[i, j];
                        TruyVet(i, k);
                        TruyVet(k, j);
                end;
    end;

    procedure InKQ;
    var i, j: integer;
    begin
        assign(f, fo); rewrite(f);
        if L[s, t] = +oo then
        begin
                writeln(f, -1);
        end
        else
        begin
                writeln(f, L[s, t]);
                TruyVet(s, t);
                writeln(f, t);
        end;

        close(f);
    end;

BEGIN
        Nhap;
        Floyd;
        InKQ;
END.