Thuật toán Floyd

THUẬT TOÁN FLOYD: XÁC ĐỊNH ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH


Bài viết sau đây được tổng hợp từ:
1) Toán rời rạc của TS. Phan Đăng Cầu (HVCNBCVT)

2) Bài giảng kỹ thuật lập trình của TS.Nguyễn Duy Phương (HVCNBCVT)


       Để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị, chúng ta có thể sử dụng n lần thuật toán Ford_Bellman hoặc Dijkstra (trong trường hợp trọng số không âm). Tuy nhiên cả 2 thuật toán này đều có độ phức tạp tính toán lớn ( chí ít là O(n^3)). Trong trường hợp tổng quát ta có thể sử dụng thuật toán Floyd. Phương pháp này được xây dựng bởi Floyd trên cơ sở sử dụng những ý tưởng của phương  pháp Warshall trong xác định bao đóng chuyển tiếp. Cụ thể ta thực hiện các bước sau:


Ta gọi Dk là ma trận chứa khoảng cách ngắn nhất từ đỉnh i đến đỉnh j trong các đường đi chỉ chứa các nút trong tập {1,2,...,k}. Ta có thể thực hiện theo từng bước sau:


Bước 0: Khởi đầu ta đặt D0[i,j] = W[i,j] là đường đi trực tiếp, không qua nút nào cả.
Bước 1: D1[i,j] = min(D0[i,j], D0[i,1] + D0[1,j])
...
Bước k:Dk[i,j] = min(D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j])
...


Đến bước n ta sẽ được ma trận D cần tìm. Trong mỗi bước ta ghi lại vết đường đi trong ma trận P[i,j]


Độ phức tạp tính toán là O(n^3).


_______________________________________________________
Chương trình có thể mô phỏng lại đơn giản như sau:


Input:  Đồ thị cho bởi ma trận trọng số a[i,j] với i, j= 1,2,...,n
Output: Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i,j] với i, j = 1,2,...,n


d[i,j] = độ dài đường đi ngắn nhất từ i đến j
Ma trận ghi nhận đường đi p[i,j] với i,j = 1,2,...,n
     Ví dụ: p[i,j] = k  ( k = 1,2,...,n) có nghĩa là trước đỉnh j là đỉnh k trong đường đi ngắn nhất từ i đến j.

(*Buoc khoi tao*)
for(i=1;i<=n;++i)
  for(j=1;j<=n;++j)
  {
  d[i][j] = a[i][j]; //Luu duong di truc tiep tu i den j
  p[i][j] = i; //Truoc dinh j la dinh i
  }
  
(*Buoc lap*)
for(k=1;k<=n;++k)
  for(i=1;i<=n;++i)
 for(j=1;j<=n;++j)
 {
  if(d[i][j] > d[i][k] + d[k][j])
  {
   d[i][j] =  d[i][k] + d[k][j];
   p[i][j] = k; //Luu vet
  }
 }

Cài đặt: Code

#include<iostream>
#include<stdlib.h>
#include<fstream>
#define MAX 100
#define TRUE 1
const int lim =   32767;
using namespace std;

ifstream fi("floyd.txt");
ofstream fo("floyd_output.txt");

int a[MAX][MAX], d[MAX][MAX], trace[MAX][MAX];
int n;

/*:
 a[][] = MTK luu do thi
 d[i][j] = Khoang cach tu dinh i den dinh j, chuong trinh se tim Min(d[i][j])
 n = chi so hang va cot cua MTK
 trace[i][j]= t =>luu vet, truoc dinh j la dinh k
 */

//Nhap ma tran
void Init()
{
 int i,j;
 //Nhap chi so hang - cot
 fi>>n;
 for(i=1;i<=n;++i)
   for(j=1;j<=n;++j)
   {
   fi>>a[i][j];
   
   }
}

//------------------------------------------------------------------------------

void Floyd()
{
 int i,j,k;
 //Khoi tao gia tri ban dau cho mang d
 for(i =1;i<=n;++i)
   for(j=1;j<=n;++j)
   {
   if(a[i][j] == -1)
       d[i][j] = lim;
   else
        {
      d[i][j] = a[i][j];
       /*Do dai duong di tu i->j la do dai duong di truc tiep tu i->j*/
       }

   trace[i][j] = i;
   
   }
   
 for(k=1;k<=n;++k)
   for(i=1;i<=n;++i)
   {
  if(d[i][k] > 0 && d[i][k]<lim)                                                  //Neu co duong di tu i den k
  for(j=1;j<=n;++j)
  {
   if(d[i][j] > d[i][k] + d[k][j])
   {
    d[i][j] = d[i][k] + d[k][j];
    trace[i][j] = k;
   }
  }
   }

}

void in_duong_di()
{
 int i,j,t;
 for( i =1;i<=n;++i)
   for( j =i+1;j<=n;++j)
   {
   fo<<endl<<"Duong di tu dinh "<<j<<" den dinh "                                   <<i<<endl;
   t = trace[i][j];
  // cout<<"Truoc dinh " <<j <<"la dinh"<<t<<endl;
   fo<<j;
   while(t!=i)
   {
    fo<<" "<<t;
    t = trace[i][t];
   }
   fo<<" "<<i;
   fo<<endl<<"Tong chi phi : "<<d[i][j];
   }
}

int main()
{
 Init();
 Floyd();
 in_duong_di();
 fi.close();
 fo.close();
 return 0;
}

Bạn có thể tải mã nguồn tại đây