Thuật toán Floyd

Bách khoa toàn thư mở Wikipedia

Bài hoặc đoạn này cần được wiki hóa theo các quy cách định dạng và văn phong Wikipedia. Xin hãy giúp phát triển bài này bằng cách liên kết trong đến các mục từ thích hợp khác.

Bài toán. Cho đồ thị vô hướng, có trọng số và không có chu trình âm. tìm đường đi cơ bản (không có đỉnh lặp lại) ngắn nhất giữa mọi cặp đỉnh (trường hợp riêng là giữa 2 đỉnh x và y, x≠y).
Thuật toán
Giả sử ma trận trọng số là A(NxN). dùng mảng A đóng thêm vai trò là mảng nhãn khoản cách ngắn nhất giữa 2 đỉnh bất kỳ: A[i,j] là khoản cách ngắn nhất giữa 2 đỉnh i và j.
Để đạt được mục đích này, xét mọi đỉnh k, nếu A[i,j]>A[i,k]+A[k,j] thì sửa lại nhãn: A[i,j]:=A[i,k]+A[k,j] và đường đi ngắn nhất từ i đến j bây giờ nên đi qua k sẽ ngắn hơn trước
Để lưu lại hành trình đường đi ngắn nhất giữa 2 đỉnh bất kỳ i và j, dùng thêm mảng G(NxN): G[i,j]:=k nếu đường đi ngắn nhất từ i đến j phải qua đỉnh k.

Chương trình
(Chạy trên Pascal mọi phiên bản, có thể sửa đổi cho phù hợp các ngôn ngữ lập trình khác)

uses crt;
const 
   fi='floyd.in';
   fo='floyd.out';
   max=100;
   vc=100*50*maxint;
type
   m1=array [1..max, 1..max] of longint;
   m2=array [1..max, 1..max] of byte;
var 
   a:m1; {ma trận trọng số A, có vai trò nhãn khoản cách ngắn nhất giữa 2 đỉnh}
   g:m2; {lưu đình trung gian, g[i,j]=k, đường đi ngắn nhất từ i tới j phải qua k}
   m:integer; {số cạnh của đồ thị}
   n,x,y:integer; {số đỉnh, đỉnh xuất phát, đỉnh đích}
   s:string; {ghi nhận hành trình}
procedure nhap;
var
   f:text;
   k,w:integer;
   i,j:byte;
begin
   assign(f,fi);
   reset(f);
   fillchar(a, sizeof(a),0);
   readln(f,n,m,x,y);
   for k:=1 to m do
   begin
      readln(f,i,j,w); {cạnh (i,j) có trọng số w}
      a[i,j]:=w;
      a[j,i]:=w;
   end;
   close(f);
end;
procedure floyd;
var i,j,k:integer;
begin
   {Khởi trị mảng nhãn A như sau:
A đóng vai trò là mãng khoản cách ngắn nhất
Mặc định: A[i,j] chính là độ dài đường nối trực tiếp từ i đến j nếu tồn tại đường này
Nếu không: khởi trị nhãn khoản cách ngắn nhất giữa 2 đỉnh i và j là vô cùng: vc
   }
   for i:=1 to n do
   for j:=1 to n do
   if a[i,j]=0 then a[i,j]:=vc;
   {Sửa mãng nhãn bằng 3 vòng for}
   for k:=1 to n do
   for i:=1 to n do
   for j:=1 to n do
   if a[i,j]>a[i,k]+a[k,j] then
   begin
      a[i,j]:=a[i,k]+a[k,j]; {ghi nhận giá trị mới giữa i và j}
      g[i,j]:=k; {ghi nhận đỉnh trung gian trên hành trình ngắn nhất từ i đến j là k}
   end;
end;
procedure find(x0,y0:byte); {Tìm hành trình ngắn nhất từ x0 đến y0}
var 
   i,x,y:byte;
   ch:char;
begin
   s:='';
   s:=s+char(x0)+char(y0); {} khởi trị xâu đường đi S, chỉ có đỉnh x0 và y0}
   i:=1;
   while i<length(s) do {chèn dần các đỉnh trung gian vào giữa các đỉnh i và i+1}
   begin
      x:=ord(s[i]);
      y:=ord(s[i+1]);
      if g[x,y]=0 then inc(i) {Không có đỉnh trung gian giữa i và i+1 thì tăng i}
      else
      begin
         ch:=char(g[x,y]); {chuyển đỉnh trung gian thành ký tự ch}
         insert(ch,s,i+1); {chèn ch vào trước ký tự s[i+1]}
      end;
   end;
end;
procedure xuat;
var 
   i:integer;
   f:text;
begin
   assign(f,fo);
   rewrite(f);
   if a[x,y]=vc then {vô nghiệm}
   begin
      writeln(f,-1);
      close(f);
      halt; {Ngắt toàn bộ, coi như đã làm xong}
   end;
   writeln(f, a[x,y]); {in độ dài đường đi ngắn nhất giữa x đến y}
   find(x,y); {tìm hành trình d9unog72 đi từ x tới y là ngắn nhất, giá trị trả về trong chuỗi toàn cục s}
   for i:=1 to length(s) do
   writeln(f,ord(s[i]));
   close(f);
end;
begin
   nhap;
   floyd;
   xuat;
end.

Nguồn
Chuyên đề bồi dưỡng HSG Tin học THPT - Ứng dụng Lý thuyết đồ thị
Tác giả: Hồ sĩ Đàm - Trần Đỗ Hùng
In tháng 7 năm 2006
Bản quyền thuộc về NXB Giáo dục