Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson 

Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson):

  • Khởi tạo một luồng bằng 0.
  • Trong khi đồ thị tăng luồng của f còn có đường đi cơ bản (đường tăng luồng), thì tìm một đường đi như thế, nâng luồng dọc theo đường đi này.
  • Khi không còn đường đi cơ bản nữa thì f là luồng cực đại.

Đoạn chương trình sau minh hoạ thuật toán Ford - Fulkerson:

1. Khởi tạo một luồng bằng 0

2. while (timduongtangluong())

/* tìm được đường tăng luồng */

{

  (a) tangluong();

  (b) hienthiduongtangluong();

}

 

Thuật toán tìm đường tăng luồng (timduongtangluong()): Sử dụng thuật toán tìm kiếm theo chiều rộng - BFS để tìm một đường tăng luồng trên đồ thị tăng luồng. Thực hiện tìm đường tăng luồng bắt đầu từ đỉnh phát s đến đỉnh thu t để tìm đường tăng luồng thì phải duyệt tất cả các đỉnh kề của đỉnh hiện tại. Nếu tìm được đường tăng luồng thì hàm trả lại giá trị là 1, ngược lại thì hàm trả lại giá trị là 0.

int timduongtangluong()

{ 1. Khởi tạo hàng đợi Q là rỗng

  2. Đánh dấu các đỉnh chưa được duyệt

  3. Thêm đỉnh s vào hàng đợi

  4. Đánh dấu là đã duyệt

  5. Trong khi hàng đợi khác rỗng (lặp)

  {

     5.a. Lấy phần tử ở đầu hàng đợi gán vào u
         5.b. Xét các đỉnh w là kề của đỉnh u (lặp)

     {

        Nếu w chưa được duyệt và có khả năng lớn
           hơn luồng thì

        - Đánh dấu w đã được duyệt

        - Nếu đỉnh w trùng với t thì

          + Trả lại giá trị là 1

          + Dừng thuật toán

        - Thêm đỉnh w vào hàng đợi

     }

  }

  6. Trả lại giá trị 0

}

Ví dụ, cho đồ thị G = (V, E) với tập đỉnh V = {1, 2, 3, 4, 5, 6}, tập cung E = {(1, 2, 6), (1, 3, 6), (1, 4, 2), (2, 4, 2), (2, 5, 3),
(3, 4, 4), (3, 6, 3), (4, 5, 10), (4, 6, 6), (5, 6, 3)}. Sử dụng thuật toán Ford - Fulkerson để tìm luồng cực đại

Giải thích tệp dữ liệu đầu vào dothi511.inp:

  • Dòng đầu tiên có giá trị là: n m s t, ví dụ: 6 8 1 6, trong đó:
  • n: số đỉnh;
  • m: số cung;
  • s: đỉnh phát;
  • t: đỉnh thu.
  • M dòng tiếp theo là cung gồm điểm đầu, điểm cuối và khả năng thông qua: u v c, ví dụ: 1 2 4, trong đó:
  • u: điểm đầu;
  • v: điểm cuối;
  • c: khả năng thông qua của cung.

- Dữ liệu đầu ra:

  • Thông tin từng bước tăng luồng;
  • Luồng trên các cung sau khi tăng luồng;
  • Luồng cực đại của đồ thị sau tăng luồng;

- Cấu trúc dữ liệu của chương trình:

  • Hàng đợi: int Q[MAX]; // Sử dụng hai biến truoc và sau để quản lý hàng đợi, hàng đợi được cài đặt bằng mảng một chiều, số phần tử tối đa là 100.
  • Mảng con trỏ: DiemDich A[max]; // Thông tin của đỉnh kề của đỉnh hiện tại A[i].
  • int c[MAX][MAX]; // Khả năng thông qua của các cung.
  • int f[MAX][MAX]; // Luồng trên các cung.
  • int duyet[MAX];  // Đánh dấu đỉnh đã duyệt.

Mô tả dữ liệu sẽ được cập nhật vào các biến từ khi bắt đầu khởi tạo và tìm đường tăng luồng.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

typedef struct DiemDich

{ int tendiem, khanang;

            //tendiem được đánh bằng số

   DiemDich *next;

};

DiemDich *A[MAX];

int  c[MAX][MAX]; // khả năng thông qua của cung

int  f[MAX][MAX]; // luồng trên các cung

int  duyet[MAX]; //đánh dấu đỉnh đã duyệt

int  n, m, s, t, k;

/* n: số đỉnh, m: số cung, s: đỉnh phát, t: đỉnh thu */

int  u, v; // u đỉnh đầu, v đỉnh cuối của cung

int  maxflow; // giá trị cực đại của luồng

int  Q[MAX]; // hàng đợi

int  truocQ, sauQ;

void hienthiLuongcucdai();

void taohangdoirong()

{    truocQ = 0; sauQ = -1;

}

int laykichthuocHangdoi()

{ return (sauQ - truocQ + 1);

}

int kiemtraHangdoirong()

{ return ((laykichthuocHangdoi() = = 0)? 1:0);

}

int kiemtraHangdoiday()

{ return (sauQ = = (MAX-1)? 1:0);

}

void themvaoHangdoi(int x)

{   if(kiemtraHangdoiday() = = 1)

     printf("\nHang doi day!");

   else

   { if(sauQ<truocQ)

     {

       sauQ = truocQ;

       Q[truocQ] = Q[sauQ] = x;

     }

     else

     { sauQ++;

       Q[sauQ] = x;

     }

  }

}

int layphantutruocHangdoi()

{ if (kiemtraHangdoirong() = = 1)

  {

     printf("\nHang doi rong!\n");

     return -1;

  }

   else

     return (Q[truocQ++]);

}

int timmin(int x,int y)

{   return ((x<y)? x:y);

}

void themDiemDich(DiemDich **flowP,int v,int c)

{    DiemDich *p = new DiemDich;

     p->tendiem = v;

     p->khanang = c;

     p->next  = (*flowP);

      (*flowP) = p;

}

void khoitaomangDuyet()

{    for(int i = 0; i<MAX; i++) duyet[i] = 0;

}

int timLuong()

{ int u, v;

  DiemDich *p;

  taohangdoirong();

  khoitaomangDuyet();

  themvaoHangdoi(s);

  duyet[s] = n+1;

  while (laykichthuocHangdoi()! = 0)

  {  u = layphantutruocHangdoi();

     p = new DiemDich;

     p = A[u];

     while(p! = NULL)

     {   int v = p->tendiem;

        if ((duyet[v] = = 0)&&(c[u][v]>f[u][v]))

        {

         duyet[v] = u;

         if (v = = t) return 1;

            themvaoHangdoi(v);

       }

        p = p->next;

    }

  }

  return 0;

}

void tangLuong()

{  int u,v,delta = 10000;

   // tìm giá trị nhỏ nhất trên các cung

   v = t;

   while (v! = s)

   { u = duyet[v];

     delta = timmin(delta,c[u][v] - f[u][v]);

     v = u;

  }

   // tăng luồng

   v = t;

   while (v! = s)

   { u = duyet[v];

     f[u][v] + = delta; // tăng luồng f = f+ delta

     f[v][u] - = delta; // cung nghịch

     v = u;

     //đổi vai trò đỉnh cuối hiện tại cung đi qua
         //  là đỉnh đầu cung tiếp theo trên đường đi

  }

}

void khoitaorongMangA()

{ for(int i = 0; i<MAX; i++) A[i] = NULL;

}

void docDulieu()

{ khoitaorongMangA();

  FILE *F = fopen("dothi511.inp","rt");

  if (F = = NULL) printf("\nTep tin rong!");

  else

  {  fscanf(F,"%d %d %d %d\n",&n,&m,&s,&t);

     for (int i = 1;i<= m;i++)

     { fscanf (F,"%d %d %d\n",&u,&v,&k);

        c[u][v] = k;

        themDiemDich(&A[u],v,k);

     }

  }

  fclose(F);

}

long int tongluong()

{ long int sum = 0;

     for (int v = 1; v<= n; v++)

        if(f[s][v]>0) sum + = f[s][v];

  return (sum);

}

void hienthiLuong()

{  for(int i = 0; i<m; i++)

   { for(int j = 0; j<m; j++)

     { if (f[i][j]>0)

          printf("\nLuong tren cung (%d, %d): %d",
                   i, j, f[i][j]);

     }

  }

printf ("\n\nLuong cuc dai: %ld\n", tongluong());

}

void main()

{

  docDulieu();

  int dem = 0;

  while (timLuong())

  {

    printf("\nTang luong lan thu %d", ++dem);

    if (timLuong() = = 0) break;

    tangLuong();

    hienthiLuong();    

  }

  hienthiLuong();

}

Tham khảo: Nguyễn Trường Xuân và các tác giả, Lý thuyết đồ thị và ứng dụng, nxb Giáo dục Việt Nan, 2017. 

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI