1. Mục đích của Floyd-Warshall Algorithm (viết tắt là F-W Algo.) là tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị vô hướng không có chu kỳ âm dựa trên khái niệm “các đỉnh trung gian”.

2. Khái niệm trung tâm của F-W Algo. là “các đỉnh trung gian”.”

3. Định nghĩa: Ký hiệu p=(x₁, x₂,…, x_k)là đường đi từ x₁ đến x_k thì mọi đỉnh x₂,…,x_k gọi là các đỉnh trung gian trên đường đi p từ x₁ đến x_k.

4. Ý tưởng chính của F-W Algo. là: Cho V={1, 2,…, n} là tập đỉnh của đồ thị và tập đỉnh U={1, 2,…, k}. Xét cặp đỉnh i,j và mọi đường đi có thể từ i đến j với các đỉnh trung gian chỉ là các đỉnh thuộc tập U. Gọi p là đường đi ngắn nhất từ i đến j với các đỉnh trung gian thuộc U. Khi đó ta có hai tình huống sau:
a. Nếu k không là đỉnh trung gian trên đường đi từ i đến j thì đường đi ngắn nhất từ i đến j có các đỉnh trung gian là {1, 2,…, k-1} cũng là đường đi ngắn nhất từ i đến j với các đỉnh trung gian là {1, 2,…, k}
b. Nếu k là một đỉnh trung gian trên đường đi từ i đến j thì ta tách đường đi p thành hai đoạn con là p₁ đi từ i đến k và p₂ đi từ k đến j. Các đoạn đường con p₁, p₂ là các đường đi ngắn nhất với các đỉnh trung gian là các đỉnh {1, 2,…, k-1}. Từ đó suy ra cách xác định độ dài của đường đi từ i đến j nhờ hệ thức sau:

c.

Trong đó dij là độ dài đường đi ngắn nhất từ i đến j; w_ij là trọng số trên đường đi ij.

Từ hệ thức trên ta thấy: để xác định độ dài đường đi ngắn nhất d_ij{1..k} từ i đến j qua các đỉnh

 Begin

       For i:=1 to n do

          For j:=1 to n do

	d[i,j]:=w[i,j];  {Trị ban đầu của biến lưu đường đi ngắn nhất là trọng sô w[i,j] }

                p[i,j]:=i; {Ghi nhớ đỉnh i đứng trước j có đưưòng đi ngắn nhất đến j}  

        End;

{Đoạn chương trình mô tả F-W Algo.}

Begin

    For k:=1 to  n do

       For i:=1 to n  do

          For j:=1 to n do

	 If  di,j]>d[i,k]+d[j,k] Then

	    Begin

                   d[i,j:=d[i,k]+d[j,k];

	          p[i,j]>p[k,j];   {k là đỉnh trung gian trên đường ngắn nhất từ i đếnj}

                         End;

        End;

6. Cài đặt trực quan (trên ngôn ngữ Pascal) cho F-W Algo. (Cài đặt này đã dùng trong nhiều năm liền để cho sinh viên CNTT một số trường công, tư lập từ Hà nội đến Đồng Hới thực hành thành công thuật toán F-W)

PROGRAM FLOYD_WARSHALL;

USES CRT,GRAPH;

CONST R=15;DL=500;N=5;VC=200;VOCUC=10000;

      C:ARRAY[1..5] OF INTEGER=(240,460,350,130,20);

      D:ARRAY[1..5] OF INTEGER=(20,240,460,460,240);

      EC:ARRAY[1..10] OF INTEGER=(350,276,204,130,405,295,240,240,185,75);

      ED:ARRAY[1..10] OF INTEGER=(130,166,166,130,360,360,240,460,360,360);

VAR   G,A,P:ARRAY[1..N,1..N] OF INTEGER;

      DAU,CUOI:INTEGER;

(*-----------------------------------------------------------------------*)

PROCEDURE INITGR;  {KHOI TAO DO HOA}

 VAR GD,GM:INTEGER;

  BEGIN

   GD:=DETECT;

   INITGRAPH(GD,GM,'..BGI');

   IF (GRAPHRESULT<> GROK) THEN

    BEGIN

     WRITELN('LOI KHOI TAO DO HOA, GO ENTER KET THUC !');

     READLN;

     HALT(1)

    END

  END;

(*-----------------------------------------------------*)

PROCEDURE VENUT(U,M1,M2:INTEGER);   {Ve cac dinh do thi}

VAR ST:STRING[3];

 BEGIN

  SETFILLSTYLE(1,M2);

  SETCOLOR(M1);

  FILLELLIPSE(C[U],D[U],R,R);

  STR(U,ST);

  OUTTEXTXY(C[U]-2,D[U]-2,ST);

 END;

(*-------------------------------*)

PROCEDURE LINK(X,Y,M1,M2:INTEGER);   {Noi cac dinh}

 VAR T:INTEGER;ST:STRING[3];

 BEGIN

  SETCOLOR(M2);

  LINE(C[X],D[X],C[Y],D[Y]);

  T:=Y-X+((X-1)*(2*N-X)) DIV 2;

  STR(G[X,Y],ST);

  SETCOLOR(M1);

  OUTTEXTXY(EC[T],ED[T],ST);

 END;

(*-------------------------------*)

PROCEDURE INIT_GRAPH; {Tu dong tao cau truc do thi mot cach ngau nhien}

 VAR I,J:INTEGER;

  BEGIN

   RANDOMIZE;

   FOR I:=1 TO N DO

    BEGIN

     G[I,I]:=0;

     FOR J:=I+1 TO N DO

      BEGIN

       IF RANDOM(2)=1 THEN G[I,J]:=10+RANDOM(VC-10)

                      ELSE G[I,J]:=VOCUC;

       G[J,I]:=G[I,J]

      END;

    END;

   FOR I:=1 TO N DO

    BEGIN

     J:=0;

     REPEAT

      J:=J+1

     UNTIL ((G[I,J]>0) AND (G[I,J]
     IF (J=N) AND ((G[I,N]=0) OR (G[I,N]=VOCUC)) THEN

      BEGIN

       J:=1+RANDOM(N);

       IF J=I THEN IF I
       G[I,J]:=10+RANDOM(VC-10);G[J,I]:=G[I,J]

      END;

    END;

  END;



(*--------------------------------------------------*)

PROCEDURE DEMO;           {Ghi cac thao tac ra man:}

 VAR K:CHAR;I:INTEGER;

  BEGIN

   SETFILLSTYLE(1,BLUE);

   BAR(480,0,GETMAXX,GETMAXY);

   SETCOLOR(YELLOW);

   OUTTEXTXY(500,30,'Nhap Hai Dinh:');

   OUTTEXTXY(500,60,'Dinh Dau, Cuoi');

   SETCOLOR(WHITE);

   OUTTEXTXY(500,105,'Dau=');

   REPEAT K:=READKEY;VAL(K,DAU,I) UNTIL I=0;

   OUTTEXTXY(540,105,K);

   OUTTEXTXY(500,150,'Cuoi=');

   REPEAT K:=READKEY;VAL(K,CUOI,I) UNTIL I=0;

   OUTTEXTXY(548,150,K);

   OUTTEXTXY(490,270,'Go Space Tim Tiep...');

   SETCOLOR(YELLOW);

   OUTTEXTXY(490,320,'Go Enter Tao Moi...');

   SETCOLOR(RED);

   OUTTEXTXY(490,370,'Go Esc Ket Thuc !');

  END;

(*--------------------------------------------------*)

PROCEDURE PRINT_GRAPH;  {In do thi}

 VAR I,J:INTEGER;

  BEGIN

   SETBKCOLOR(BLUE);CLEARDEVICE;

   SETFILLSTYLE(1,DARKGRAY);

   BAR(0,0,GETMAXY,GETMAXY);

   FOR I:=1 TO N DO

    BEGIN

     FOR J:=I+1 TO N DO

     IF (G[I,J]>0) AND (G[I,J]
     VENUT(I,YELLOW,BLUE);

    END;

  END;

(*---------------------------------------------------------*)

PROCEDURE FLOYLD_WARSHALL;  {Thuat toan Floyld_Warshall}

 VAR I,J,K:INTEGER;

 BEGIN

  FOR I:=1 TO N DO

  FOR J:=1 TO N DO

   BEGIN

    A[I,J]:=G[I,J];

    P[I,J]:=0;

   END;

  FOR K:=1 TO N DO

  FOR I:=1 TO N DO

  FOR J:=1 TO N DO

   IF A[I,K]+A[K,J]
    BEGIN

     A[I,J]:=A[I,K]+A[K,J];  {Day la duong di min}

     P[I,J]:=K;              {Ghi nho dinh k vao mang P}

    END;

 END;

(*------------------------------*)

PROCEDURE SEARCHD(D1,D2:INTEGER);

 VAR ST:STRING[20];

 BEGIN

  IF P[D1,D2]=0 THEN

   BEGIN

    VENUT(D1,BLUE,YELLOW);DELAY(DL);

    VENUT(D2,BLUE,YELLOW);DELAY(DL);

   END ELSE

    BEGIN

     SEARCHD(D1,P[D1,D2]);

     SEARCHD(P[D1,D2],D2);

    END;

 END;

(*-----------------------------------------------*)

PROCEDURE SEARCH;

 VAR ST:STRING[20];

 BEGIN

  IF A[DAU,CUOI]=VOCUC THEN ST:='Khong Co Duong Di !' ELSE

   BEGIN

    STR(A[DAU,CUOI],ST);

    ST:='Min = '+ST;

    SEARCHD(DAU,CUOI);

   END;

  SETCOLOR(RED);

  OUTTEXTXY(490,210,ST);

 END;

(*-------------------------------------------------------*)

PROCEDURE TRAVERSE;

 VAR K:CHAR;

 BEGIN

   IF KEYPRESSED THEN

   REPEAT K:=READKEY UNTIL NOT KEYPRESSED;

   REPEAT

    INIT_GRAPH;

    FLOYLD_WARSHALL;

     REPEAT

      PRINT_GRAPH;

      DEMO;

      SEARCH;

      K:=READKEY;

     UNTIL (K=#27) OR (K=#13);

   UNTIL (K=#27);

 END;

(*--------------------------------------*)

BEGIN (* CHUONG TRINH CHINH *)

  CLRSCR;

  INITGR;

  TRAVERSE;

  CLOSEGRAPH;

END.

Tài liệu tham khảo

1. Kenneth H.Rosen- Discrete Mathematics and

Its applications. MacGraw Hill, 1994. (bản dịch tiếng Việt- Chương 7 - Đồ thị)

2. Robert Sedgewick- Algorithms. (bản dịch tiếng Việt- Phần 6-Các thuật toán đồ thị).

3. Mark Allen Weiss- Data Structure and Algorithms Analysis in C++. Second Edition. Edition-Wesley.
(Chapter 9 Graph Algorithms)

4. Nguyễn Thanh Hùng, Nguyễn Đức Nghĩa. Giáo trình Lý thuyết đồ thị. NXB ĐH QG Hồ Chí Minh. 2005

School@net