Giải thuật và lập trình - C: V. Một số bài toán trên đồ thị

1. Bài toán tìm đuờng đi ngắn nhất từ một đỉnh của đồ thị   (the single source shorted path problem)

Cho đồ thị G với tập các đỉnh V và tập các cạnh E (đồ thị có hướng hoặc vô hướng). Mỗi cạnh của đồ thị có một nhãn, đó là một giá trị không âm, nhãn này còn gọi là giá (cost) của cạnh. Cho trước một đỉnh v xác định, gọi là đỉnh nguồn. Vấn đề là tìm đường đi ngắn nhất từ v đến các đỉnh còn lại của G; tức là các đường đi từ v đến các đỉnh còn lại với tổng các giá (cost) của các cạnh trên đường đi là nhỏ nhất. Chú ý rằng nếu đồ thị có hướng thì đường đi này là đường đi có hướng.

Ta có thể giải bài toán này bằng cách xác định một tập hợp S chứa các đỉnh mà khoảng cách ngắn nhất từ nó đến đỉnh nguồn v đã biết. Khởi đầu S={v}, sau đó tại mỗi bước ta sẽ thêm vào S các đỉnh mà khoảng cách từ nó đến v là ngắn nhất. Với giả thiết mỗi cung có một giá không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua các đỉnh đã tồn tại trong S. Để chi tiết hoá giải thuật, giả sử G có n đỉnh và nhãn trên mỗi cung được lưu trong mảng hai chiều C, tức là C[i,j] là giá (có thể xem như độ dài) của cung (i,j), nếu i và j không nối nhau thì C[i,j]=∞. Ta dùng mảng 1 chiều D có n phần tử để lưu độ dài của đường đi ngắn nhất từ mỗi đỉnh của đồ thị đến v. Khởi đầu khoảng cách này chính là độ dài cạnh (v,i), tức là D[i]=C[v,i]. Tại mỗi bước của giải thuật thì D[i] sẽ được cập  nhật lại để lưu độ dài đường đi ngắn nhất từ đỉnh v tới đỉnh i, đường đi này chỉ đi qua các đỉnh đã có trong S.

Để cài đặt giải thuật dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n, tức là V={1,..,n} và đỉnh nguồn là 1. Dưới dây là giải thuật Dijkstra để giải bài toán trên.

void Dijkstra() {
  S = [1]; //Tập hợp S chỉ chứa một đỉnh nguồn
  for (i =2; i<=n; i++)
    D[i-1] = C[0,i-1]; //khởi đầu các giá trị cho D
  for (i=1; i<n; i++) {
    Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất;
    Thêm w vào S;
    for (mỗi đỉnh u thuộc V-S)
      D[u-1] = min(D[u-1], D[w-1] + C[w-1,u-1]);
  }
}

Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi này từ đỉnh nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u]=w với u là đỉnh "trước" đỉnh w trong đường đi. Lúc khởi đầu P[u]=1 với mọi u.

Giải thuật Dijkstra được viết lại như sau:

void Dijkstra() {   
  S =[1]; //S chỉ chứa một đỉnh nguồn
  for(i=2; i<=n; i++) {
    P[i-1] =1; //khởi tạo giá trị cho P
    D[i-1] =C[0,i-1]; //khởi đầu các giá trị cho D
  }
  for (i=1; i<n; i++) {
     Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất;
     Thêm w vào S;
     for (mỗi đỉnh u thuộc V-S)
       if  (D[w-1] + C[w-1,u-1] < D[u-1]){
         D[u-1] =D[w-1] + C[w-1,u-1];
         P[u-1] =w;
       }
   }
}

Ví dụ: áp dụng giải thuật Dijkstra cho đồ thị hình V.5 dưới đây:

Kết quả khi áp dụng giải thuật:

Mảng P có giá trị như sau:

Từ kết quả trên ta có thể suy ra rằng đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là 1 → 4 → 3 có độ dài là 40. đường đi ngắn nhất từ 1 đến 5 là 1 → 4 → 3 → 5 có độ dài 50.

2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh

Giả sử đồ thị G có n đỉnh được đánh số từ 1 đến n. Khoảng cách hay giá giữa các cặp đỉnh được cho trong mảng C[i,j]. Nếu hai đỉnh i,j không được nối thì C[i,j]= ¥. Giải thuật Floyd xác định đường đi ngắn nhất giữa hai cặp đỉnh bất kỳ bằng cách lặp k lần, ở lần lặp thứ k sẽ xác định khoảng cách ngắn nhất giữa hai đỉnh i,j theo công thức:

Ak[i,j]=min(Ak-1[i,j], Ak- 1[i,k]+Ak-1[k,j])

Ta cũng dùng mảng P để lưu các đỉnh trên đường đi.

float A[n,n], C[n,n];
int P[n,n];
void Floyd(){
  int i,j,k;
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++){
      A[i-1,j-1] = C[i-1,j-1];
      P[i-1,j-1]=0;
    }
  for (i=1; i<=n; i++)
    A[i-1,i-1]=0;
  for (k=1; k<=n; k++)
    for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
        if (A[i-1,k-1] + A[k-1,j-1] < A[i-1,j-1){
          A[i-1,j-1] = A[i-1,k-1] + A[k-1,j-1];
          P[i-1,j-1] = k;
        }
}

3. Bài toán tìm bao đóng chuyển tiếp (transitive closure)

Trong một số trường hợp ta chỉ cần xác định có hay không có đường đi nối giữa hai đỉnh i,j bất kỳ. Giải thuật Floyd có thể đặc biệt hoá để giải bài toán này. Bây giờ khoảng cách giữa i,j là không quan trọng mà ta chỉ cần biết i,j có nối nhau không do đó ta cho C[i,j]=1 (~true) nếu i,j được nối nhau bởi một cạnh, ngược lại C[i,j]=0 (~false). Lúc này mảng A[i,j] không cho khoảng cách ngắn nhất giữa i,j mà nó cho biết là có đường đi từ i đến j hay không. A gọi là bao đóng chuyển tiếp của đồ thị G có biểu diễn ma trận kề là C. Giải thuật Floyd sửa đổi như trên gọi là giải thuật Warshall.

int A[n,n], C[n,n];
void Warshall(){
  int i,j,k;
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
      A[i-1,j-1] = C[i-1,j-1];
    for (k=1; k<=n; k++)
      for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
          if (A[i-1,j-1] == 0)
            A[i-1,j-1] = A[i-1,k-1] && A[k-1,j-1];
}

4. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree)

Giả sử ta có một đồ thị vô hướng G=(V,E). Đồ thị G gọi là liên thông nếu tồn tại đường đi giữa hai đỉnh bất kỳ. Bài toán tìm cây bao trùm tối thiểu (hoặc cây phủ tối thiểu) là tìm một tập hợp T chứa các cạnh của một đồ thị liên thông G sao cho V cùng với tập các cạnh này cũng là một đồ thị liên thông, tức là (V,T) là một đồ thị liên thông. Hơn nữa tổng độ dài các cạnh trong T là nhỏ nhất. Một thể hiện của bài toán này trong thực tế là bài toán thiết lập mạng truyền thông, ở đó các đỉnh là các thành phố còn các cạnh của cây bao trùm là đường nối mạng giữa các thành phố.

Giả sử G có n đỉnh được đánh số 1..n. Giải thuật Prim để giải bài toán này như sau: Bắt đầu, tập ta khởi tạo tập U bằng 1 đỉnh nào đó, đỉnh 1 chẳng hạn, U = {1}, T=U

Sau đó ta lặp lại cho đến khi U=V, tại mỗi bước lặp ta chọn cạnh nhỏ nhất (u,v) sao cho  u thuộc U và v thuộc V-U. Thêm v vào U và (u,v) vào T. Khi giải thuật kết thúc thì (U,T) là một cây phủ tối tiểu.

Ví dụ, áp dụng giải thuật Prim để tìm cây bao trùm tối thiểu của đồ thị liên thông hình V.6.

• Bước khởi đầu: U={1}, T=Æ.
• Bước kế tiếp ta có cạnh (1,3)=1 là cạnh ngắn nhất thoả mãn điều kiện trong giải  thuật Prim nên: U={1,3}, T={(1,3)}.
• Kế tiếp thì cạnh (3,6)=4 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim nên: U={1,3,6}, T={(1,3),(3,6)}.
• Kế tiếp thì cạnh (6,4)=2 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim nên: U={1,3,6,4}, T={(1,3),(3,6),(6,4)}.
• Tiếp tục, cạnh (3,2)=5 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim nên: U={1,3,6,4,2}, T={(1,3),(3,6),(6,4),(3,2)}.
• Cuối cùng, cạnh (2,5)=3 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim nên: U={1,3,6,4,2,5}, T={(1,3),(3,6),(6,4),(3,2),(2,5)}. Giải thuật dừng và ta có cây bao trùm như trong hình V.7.

Giải thuật Prim được viết lại như sau:

void Prim(graph G, set_of_edges *T) {
  set_of_vertices U; //tập hợp các đỉnh
  vertex u,v;   //u,v là các đỉnh
  T = ø;
  U = [1];
  while (U!=V){     // V là tập hợp các đỉnh của G
    gọi (u,v) là cạnh ngắn nhất sao cho u thuộc U và v thuộc V-U;
    U = U Ս [v];
    T = T Ս [(u,v)];
  }
}

Bài toán cây bao trùm tối thiểu còn có thể được giải bằng giải thuật Kruskal như sau:

Khởi đầu ta cũng cho T=ø giống như trên, ta thiết lập đồ thị khởi đầu G'=(V,T).

Xét các cạnh của G theo thứ tự độ dài tăng dần. Với mỗi cạnh được xét ta sẽ đưa nó vào T nếu nó không làm cho G' có chu trình.

Ví dụ áp dụng giải thuật Kruskal để tìm cây bao trùm cho đồ thị hình V.6. Các cạnh của đồ thị được xếp theo thứ tự tăng dần là:

(1,3)=1, (4,6)=2, (2,5)=3, (3,6)=4, (1,4)=(2,3)=(3,4)=5, (1,2)=(3,5)= (5,6)=6.

• Bước khởi đầu T = ø
• Lần lặp 1: T={(1,3)}
• Lần lặp 2: T={(1,3),(4,6)}
• Lần lặp 3: T={(1,3),(4,6),(2,5)}
• Lần lặp 4: T={(1,3),(4,6),(2,5),(3,6)}
• Lần lặp 5:

Cạnh (1,4) không được đưa vào T vì nó sẽ tạo ra chu trình 1,3,6,4,1.

Kế tiếp cạnh (2,3) được xét và được đưa vào T.

T={(1,3),(4,6),(2,5),(3,6),(2,3)}

Không còn cạnh nào có thể được đưa thêm vào T mà không tạo ra chu trình. Vậy ta có cây bao trùm tối thiểu cũng giống như trong hình V.7.