Các thuật toán về tìm đường đi ngắn nhất

83 / 100

Các thuật toán về tìm đường đi ngắn nhất

Các thuật toán về tìm đường đi ngắn nhất

Tác giả:

  • Trần Hoài An – THPT Hoàng Lê Kha, Tây Ninh

Giới thiệu

Bài toán tìm đường đi ngắn nhất trên đồ thị là một trong những bài toán đa dạng, có nhiều ứng dụng thực tế (như trong Google Maps, hay các bài toán networking, …). Các dạng bài về tìm đường đi ngắn nhất cũng thường xuyên có mặt trong các kì thi lập trình.

Bài viết này sẽ giới thiệu ba thuật toán cơ bản của dạng bài tìm đường đi ngắn nhất:

  • Thuật toán Bellman – Ford.
  • Thuật toán Dijkstra.
  • Thuật toán Floyd-Warshall (còn gọi là thuật toán Floyd).

Cần lưu ý rằng, có một thuật toán thông dụng khác cũng có tên thường gọi là thuật toán Floyd, dùng để tìm chu trình trong đồ thị có hướng. Bài viết này sẽ chỉ đề cập đến thuật toán tìm đường đi ngắn nhất.

1. Thuật toán Bellman – Ford

Thuật toán Bellman-Ford dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị có thể có trọng số âm.

Bài toán.

Cho đồ thị có hướng NN đỉnh và MM cạnh, và một đỉnh nguồn là đỉnh SS. Mỗi cạnh có trọng số nguyên. Trọng số này có thể âm hoặc dương hoặc bằng 0. Với mỗi đỉnh uu từ 11 đến NN. Yêu cầu xuất kết quả tại mỗi đỉnh uu như sau:

  1. Nếu không tồn tại đường đi từ SS đến uu thì in ra: Impossible
  2. Nếu tồn tại đường đi từ SS đến uu nhưng không có đường đi ngắn nhất in ra: -Infinity
  3. Trường hợp còn lại in ra đường đi ngắn nhất từ SS đến uu.

Input: Dòng đầu tiên gồm 3 số nguyên N,M,SN,M,SMM dòng tiếp theo, mỗi dòng gồm ba số nguyên u,v,Wu,vu,v,Wu,v biểu diễn một cạnh một chiều từ uu đến vv với trọng số là Wu,vWu,v.

Output: gồm NN dòng cho biết đường đi ngắn nhất từ đỉnh SS đến các đỉnh từ 00 đến N1N−1

Giới hạn bài toán : 1N1000,1M50001≤N≤1000,1≤M≤5000

Sample Input

7 6 4
0 1 7
2 0 1
1 2 -9
2 5 1000
3 0 7
4 3 3

Sample Output

-Infinity
-Infinity
-Infinity
3
0
-Infinity
Impossible

Khái niệm về chu trình âm

  • Chu trình âm là một chu trình trong đó tổng trọng số các cạnh là số âm. Ví dụ trong hình dưới, ta có một chu trình âm 0120→1→2 có tổng trọng số là 79+1=17−9+1=−1

  • Nếu trên đường đi từ uu đến vv chứa chu trình âm thì độ dài đường đi ngắn nhất từ uu đến vv sẽ là −∞. Vì vậy nên sự xuất hiện của chu trình âm trong đồ thị sẽ khiến một số cặp đỉnh không tồn tại đường đi ngắn nhất (chỉ tồn tại đường đi có độ dài âm vô cực).

    • Ví dụ: Ở đồ thị trên, đường đi ngắn nhất từ 44 đến 55 sẽ có cách đi là vô hạn lần qua chu trình âm đã nhắc đến, sau đó mới đi đến 55. Như vậy không có đường đi ngắn nhất.

Ý tưởng của thuật toán.

Xét trường hợp đơn giản hơn, khi đồ thị không có trọng số âm (tức đường đi ngắn nhất luôn tồn tại).

Thuật toán Bellman-Ford sẽ lặp nhiều lần. Ở mỗi vòng lặp, ta sẽ đi qua tất cả các cạnh (u,v)(u,v) trên đồ thị, so sánh đường đi SvS→v đã tìm được với đường đi SuvS→u→v

  • Ví dụ đồ thị sau:

  • Giả sử ta tìm được đường đi từ 131→3 có độ dài là 44, và đường đi từ 121→2 có độ dài là 22. Như vậy ta có thể sử dụng cạnh (2,3)(2,3) để nối dài đường đi 121→2 thành 1231→2→3 có độ dài bằng 33, tốt hơn đường đi trực tiếp 131→3 ta đã tìm được.

Có thể chứng minh được rằng, vòng lặp trên cần thực hiện N1N−1 lần, mỗi lần đi qua toàn bộ MM cạnh, là sẽ đủ để tìm đường đi ngắn nhất.

  • Chứng minh: Nhận xét rằng một đường đi ngắn nhất bất kì sẽ không có đỉnh nào được đi lại quá một lần. Như vậy một đường đi ngắn nhất sẽ không có quá N1N−1 cạnh. Việc thực hiện phép tính Dv=Du+Wu,vDv=Du+Wu,v cũng đồng nghĩa với thêm một cạnh uvu→v vào hành trình đi từ ss đến vv. Vậy một DuDu chỉ có thể được tối ưu tối đa N1N−1 lần, và từ lần thứ NN trở đi sẽ không thể tối ưu hơn được nữa.

Cài Đặt

Ở thuật toán này, đồ thị thường được lưu ở dạng danh sách cạnh.

  • Định nghĩa W[u,v]W[u,v] là trọng số cạnh nối từ đỉnh uu đến đỉnh vv (nếu có).

  • Định nghĩa mảng D[u]D[u] là đường đi ngắn nhất từ sus→u. Ban đầu, chưa có đường đi nào, D[u]=D[u]=∞ với mọi uu, ngoại trừ D[s]=0D[s]=0.

    • Nếu cần tìm lại chính đường đi ngắn nhất, ta có thể định nghĩa thêm một mảng truy vết trace[u]trace[u]. Ban đầu mọi trace[u]trace[u] bằng 1−1 nghĩa là chưa có đường đi.
  • Thực hiện N1N−1 lần: Xét lần lượt các cạnh (u,v)(u,v) trong đồ thị. Nếu D[u]+W[u,v]<D[v]D[u]+W[u,v]<D[v], cập nhật D[v]=D[u]+W[u,v])D[v]=D[u]+W[u,v]), đồng thời cập nhật trace[v]=utrace[v]=u.

  • Độ phức tạp: Ta có một vòng lặp được thực hiện N1N−1 lần, mỗi lần lặp ta sẽ xử lí tất cả các cạnh trong đồ thị, như vậy độ phức tạp của thuật toán là O(NM)O(N∗M).

Code:

const long long INF = 2000000000000000000LL;
struct Edge {
    int u, v;
    long long w; // cạnh từ u đến v, trọng số w
};
void bellmanFord(int n, int S, vector<Edge> &e, vector<long long> &D, vector<int> &trace) {
    // e: danh sách cạnh
    // n: số đỉnh
    // S: đỉnh bắt đầu
    // D: độ dài đường đi ngắn nhất
    // trace: mảng truy vết đường đi
    // INF nếu không có đường đi
    // -INF nếu có đường đi âm vô tận
    D.resize(n, INF);
    trace.resize(n, -1);

    D[S] = 0;
    for(int T = 1; T < n; T++) {
        for (auto E : e) {
            int u = E.u;
            int v = E.v;
            long long w = E.w;
            if (D[u] != INF && D[v] > D[u] + w) {
                D[v] = D[u] + w;
                trace[v] = u;
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Thao tác tìm đường đi ngắn nhất từ SS đến uu khá đơn giản, ta sẽ bắt đầu từ đỉnh uu, sau đó truy vết theo mảng tracetrace ngược về SS.

vector<int> trace_path(vector<int> &trace, int S, int u) {
    if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi

    vector<int> path;
    while (u != -1) { // truy vết ngược từ u về S
        path.push_back(u);
        u = trace[u];
    }
    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S
    
    return path;
}

Các trường hợp có chu trình âm

Thuật toán Bellman-Ford có thể xử lí được thêm trường hợp nhận biết chu trình âm, cũng như nhận biết nếu không tồn tại đường đi ngắn nhất đến một đỉnh.

Nhận biết đường đi âm vô cực

  • Nhận xét tiếp rằng, ta có thể chạy vòng quanh chu trình âm liên tục để được đường đi ngắn hơn. Như vậy thuật toán Bellman-Ford ở vòng lặp thứ NN trở đi vẫn sẽ liên tục tối ưu được đường đi, thay vì dừng lại ở lần thứ N1N−1.

    • Ta chỉ cần chạy thuật toán Bellman-Ford thêm một lần nữa với NN vòng lặp, những đỉnh nào vẫn còn tối ưu được ở lần chạy thứ hai sẽ tối ưu được mãi mãi, và đó là các đỉnh không tồn tại đường đi ngắn nhất.

Code:

// sau khi chạy xong N-1 vòng lặp Bellman-Ford 
for(int T = 0; T < n; T++){
    for (auto E : e) {
        int u = E.u;
        int v = E.v;
        long long w = E.w;
        if (D[u] != INF && D[v] > D[u] + w) {
            // vẫn còn tối ưu được --> âm vô cực
            D[v] = -INF;
            trace[v] = u;
        }
    }
}

Tìm chu trình âm

Một số bài toán có thể yêu cầu ta tìm một chu trình âm bất kì trong đồ thị. Ta có thể chỉnh sửa thuật toán Bellman-Ford lại như sau:

  • Thay vì chạy NN vòng lặp Bellman-Ford như trường hợp trên, ta chỉ cần chạy một vòng lặp. Như vậy là đủ để phát hiện ít nhất một đỉnh có đường đi bằng −∞ (nếu có).
  • Tiến hành truy vết: Bắt đầu từ đỉnh uu bất kì có đường đi bằng −∞, ta sẽ truy vết theo mảng tracetrace:

    • Trước hết gán u=trace[u]u=trace[u] đủ NN lần.

      • Mục đích của bước này là để uu chắc chắn thuộc chu trình âm. Ban đầu có thể đỉnh uu có đường đi bằng −∞ nhưng chưa chắc thuộc chu trình âm. Ví dụ trường hợp sau:

      Ở đây, từ 00 đến 11 có độ dài đường đi ngắn nhất bằng −∞, tuy nhiên đỉnh 11 lại không thuộc chu trình âm nào.

    • Sau đó, uu sẽ thuộc một chu trình âm. Ta chỉ cần truy vết đỉnh uu theo mảng tracetrace cho đến khi gặp lại chính nó, sẽ được một chu trình.
  • Chu trình vừa truy vết chính là một chu trình âm của đồ thị. Lưu ý ta vẫn phải đảo ngược kết quả truy vết, vì ta đang truy vết ngược so với đồ thị gốc.
bool findNegativeCycle(int n, vector<long long> &D, vector<int> &trace, vector<int> &negCycle) {
    // mảng D và trace đã được chạy qua thuật toán Bellman-Ford
    int negStart = -1; // đỉnh bắt đầu
    for (auto E : e) {
        int u = E.u;
        int v = E.v;
        long long w = E.w;
        if (D[u] != INF && D[v] > D[u] + w) {
            D[v] = -INF; 
            trace[v] = u;
            negStart = v; // đã tìm thấy -INF
        }
    }

    if (negStart == -1) return false; // không có chu trình âm

    int u = negStart;
    for (int i = 0; i < n; i++) {
        u = trace[u]; // đưa u về chu trình âm
    }

    negCycle = vector<int>(1, u);
    for (int v = trace[u]; v != u; v = trace[u]) {
        negCycle.push_back(v); // truy vết một vòng
    }
    reverse(negCycle.begin(), negCycle.end());
    
    return true;
}

2. Thuật toán Dijkstra

Thuật toán Dijkstra dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị trọng số không âm.

Bài toán.

Cho một đồ thị có hướng với NN đỉnh (được đánh số từ 00 đến N1N−1), MM cạnh có hướng, có trọng số, và một đỉnh nguồn SSTrọng số của tất cả các cạnh đều không âm. Yêu cầu tìm ra đường đi ngắn nhất từ đỉnh SS tới tất cả các đỉnh còn lại (hoặc cho biết nếu không có đường đi).

Sample Input

7 8 0
0 2 7
0 1 1
0 3 4
2 5 8
5 3 3
4 5 6
1 4 3
2 4 3

Sample Output

0
1
7
4
4
10
-1

Hình ảnh của Test ví dụ. Ở đồ thị này, đỉnh nguồn là đỉnh 00, đường đi ngắn nhất từ 00 đến các đỉnh 00 đến 55 là [0,1,7,4,4,10][0,1,7,4,4,10]. Riêng đỉnh 66 không có đường đi đến.

Ý tưởng của thuật toán.

Giống như thuật toán Bellman-Ford, thuật toán Dijkstra cũng tối ưu hóa đường đi bằng cách xét các cạnh (u,v)(u,v), so sánh hai đường đi SvS→v sẵn có với đường đi SuvS→u→v.

Thuật toán hoạt động bằng cách duy trì một tập hợp các đỉnh trong đó ta đã biết chắc chắn đường đi ngắn nhất. Mỗi bước, thuật toán sẽ chọn ra một đỉnh uu mà chắc chắn sẽ không thể tối ưu hơn nữa, sau đó tiến hành tối ưu các đỉnh vv khác dựa trên các cạnh (u,v)(u,v) đi ra từ đỉnh uu. Sau NN bước, tất cả các đỉnh đều sẽ được chọn, và mọi đường đi tìm được sẽ là ngắn nhất.

Cụ thể hơn, thuật toán sẽ duy trì đường đi ngắn nhất đến tất cả các đỉnh. Ở mỗi bước, chọn đường đi SuS→u có tổng trọng số nhỏ nhất trong tất cả các đường đi đang được duy trì. Sau đó tiến hành tối ưu các đường đi SvS→v bằng cách thử kéo dài thành SuvS→u→v như đã mô tả trên.

Minh họa thuật toán

Ta sẽ minh họa thuật toán bằng một đồ thị như hình. Định nghĩa:

  • DuDu là đường đi ngắn nhất từ đỉnh nguồn đên đỉnh uu đã tìm được.
  • PuPu nhận hai giá trị truetruefalsefalse cho biết đỉnh PuPu đã được chọn để tối ưu chưa.

Đỉnh được tô đen (đỉnh 0) sẽ là đỉnh nguồn.

Ban đầu, D=[0,,,]D=[0,∞,∞,∞]P=[false,false,false,false]P=[false,false,false,false]

  • Bước 1: Thuật toán sẽ chọn đỉnh 00, vì D0=0D0=0 là nhỏ nhất thỏa mãn P0=falseP0=false. Tiến hành tối ưu các cạnh đi ra:

    • Cạnh (0,2)(0,2): cập nhật D2=min(D2,D0+W0,2)=min(,0+1)=1D2=min(D2,D0+W0,2)=min(∞,0+1)=1
    • Cạnh (0,3)(0,3): cập nhật D3=min(D3,D0+W0,3)=min(,0+4)=4D3=min(D3,D0+W0,3)=min(∞,0+4)=4

Sau bước này, D=[0,,1,4]D=[0,∞,1,4]P=[true,false,false,false]P=[true,false,false,false]

  • Bước 2: thuật toán sẽ chọn ra đỉnh 22, có D2=1D2=1 là nhỏ nhất thỏa mãn P2=falseP2=false. Tiến hành tối ưu các cạnh đi ra:

    • Cạnh (2,1)(2,1): cập nhật D1=min(D1,D2+W2,1)=min(,1+3)=4D1=min(D1,D2+W2,1)=min(∞,1+3)=4
    • Cạnh (2,3)(2,3): cập nhật D3=min(D3,D2+W2,3)=min(4,1+2)=3D3=min(D3,D2+W2,3)=min(4,1+2)=3

Sau bước này, D=[0,4,1,3]D=[0,4,1,3]P=[true,false,true,false]P=[true,false,true,false]

  • Bước 3: thuật toán sẽ chọn ra đỉnh 33, có D3=1D3=1 là nhỏ nhất thỏa mãn P3=falseP3=false. Tiến hành tối ưu các cạnh đi ra:

    • Cạnh (3,1)(3,1): cập nhật D1=min(D1,D3+W3,1)=min(4,3+2)=4D1=min(D1,D3+W3,1)=min(4,3+2)=4

Sau bước này, D=[0,4,1,3]D=[0,4,1,3]P=[true,false,true,true]P=[true,false,true,true]

  • Bước 4: thuật toán sẽ chọn đỉnh 11. Không có cạnh nào đi ra.

Đến đây, tất cả các đỉnh đều đã được đánh dấu. Thuật toán kết thúc. Đường đi ngắn nhất tìm được từ đỉnh 00 là D=[0,4,1,3]D=[0,4,1,3].

Cài đặt

Ở thuật toán này, ta sẽ lưu đồ thị dưới dạng danh sách kề. Ta định nghĩa như sau:

  • D[u]D[u] là đường đi ngắn nhất từ sus→u. Ban đầu khởi tạo D[u]=D[u]=∞ với mọi uu, riêng D[s]=0D[s]=0.

    • Cũng như thuật toán Bellman-Ford, ta có thể định nghĩa thêm mảng tracetrace để truy vết đường đi nếu cần.
  • W[u,v]W[u,v] là trọng số cạnh trên đường đi từ uvu→v.
  • P[u]P[u] là mảng đánh dấu các đỉnh uu đã được xử lí chưa. Ban đầu tất cả các giá trị đều là false.

Ta sẽ lặp NN lần quá trình sau:

  • Tìm đỉnh uu có D[u]D[u] nhỏ nhất và P[u]=falseP[u]=false.
  • Sau khi tìm được đỉnh uu, ta xét các đỉnh vv kề với đỉnh uu và tiến hành tối ưu hóa D[v]D[v]: nếu D[v]>D[u]+W[u,v]D[v]>D[u]+W[u,v] thì D[v]=D[u]+W[u,v]D[v]=D[u]+W[u,v].

    • Nếu việc tối ưu hóa diễn ra, ta sẽ cập nhật trace[v]=utrace[v]=u.
  • Đánh dấu P[u]=trueP[u]=true, nghĩa là đỉnh uu đã được xử lí xong

Độ phức tạp thuật toán: Ta có NN lần lặp:

  • Bước đầu tiên có độ phức tạp O(N)O(N) mỗi lần lặp.
  • Bước thứ hai có tổng độ phức tạp O(M)O(M) qua tất cả các lần lặp

Như vậy độ phức tạp của cách cài đặt cơ bản sẽ là O(N2+M)O(N2+M).

Code:

const long long INF = 2000000000000000000LL;
struct Edge{
    int v;
    long long w;
};
void dijkstra(int n, int S, vector<vector<Edge>> E, vector<long long> &D, vector<int> &trace) {
    D.resize(n, INF);
    trace.resize(n, -1);
    
    vector<bool> P(n, 0);
    D[S] = 0;
    
    for (int i = 0; i < n; i++) {
        int uBest; // tìm đỉnh u chưa dùng, có khoảng cách nhỏ nhất
        long long Max = INF;
        for (int u = 0; u < n; u++) {
            if(D[u] < Max && P[u] == false) {
                uBest = u;
                Max = D[u];
            }
        }
        
        // cải tiến các đường đi qua u
        int u = uBest;
        P[u] = true;
        for(auto x : E[u]) {
            int v = x.v;
            long long w = x.w;
            if(D[v] > D[u] + w) {
                D[v] = D[u] + w;
                trace[v] = u;
            }
        }
    }
}

Cải tiến đối với đồ thị thưa

  • Nhận xét rằng bước đầu tiên: “Tìm đỉnh uu có DuDu nhỏ nhất và Pu=falsePu=false“, có thể được cải tiến. Ta có thể sử dụng cấu trúc dữ liệu Heap (cụ thể là Min Heap) hoặc cây nhị phân tìm kiếm để cải tiến bước này.

    • Mỗi lần tối ưu hóa DvDv, ta đẩy cặp Dv,vDv,v vào trong Heap.
    • Để tìm đỉnh có DuDu nhỏ nhất, ta chỉ cần liên tục lấy phần tử trên cùng trong Heap ra, cho đến khi gặp đỉnh uu thỏa mãn Pu=falsePu=false.
  • Mỗi lần tối ưu DvDv, ta phải push vào Heap một lần. Với mỗi lần push vào trong Heap, ta đều phải pop ra lại một lần. Do có tối đa O(M)O(M) lần tối ưu, độ phức tạp của thuật toán là O(MlogN)O(MlogN).

Độ phức tạp sau khi cải tiến: O(MlogN)O(MlogN)Lưu ý rằng với MM lớn thì độ phức tạp này không tốt hơn cài đặt cơ bản. Chứng minh như sau:

  • Ta có độ phức tạp của hai cách cài đặt:
    • Cách cài đặt cơ bản: O(N2+M)O(N2+M).
    • Cách cài đặt cải tiến: O(MlogN)O(MlogN).
  • Số lượng cạnh MM trong đơn đồ thị không vượt quá N2N2, như vậy độ phức tạp của cách cơ bản có thể được viết đơn giản thành O(N2)O(N2).
  • Để cách cài đặt cải tiến tốt hơn, ta cần MlogN<N2MlogN<N2 suy ra M<N2/logNM<N2/logN.

    • Ví dụ: đối với N=105N=105, ta cần M>6108M>6⋅108 để cách cài đặt cơ bản tốt hơn cách cài đặt cải tiến. Thực tế trong lập trình thi đấu khó có đồ thị nào có số cạnh lớn như vậy. Vì thế nhìn chung khi NN lớn thì thuật O(MlogN)O(MlogN) luôn tốt hơn.

Code:

const long long INF = 2000000000000000000LL;
struct Edge{// kiểu dữ liệu tự tạo để lưu thông số của một cạnh.
    int v;
    long long w;
};
struct Node{// kiểu dữ liệu để lưu đỉnh u và độ dài của đường đi ngắn nhất từ s đến u.
    int u;
    long long Dist_u;
};
struct cmp{
    bool operator() (Node a, Node b) {
        return a.Dist_u > b.Dist_u;
    }
};
void dijkstraSparse(int n, int s, vector<vector<Edge>> &E, vector<long long> &D, vector<int> &trace) {
    D.resize(n, INF);
    trace.resize(n, -1);
    vector<bool> P(n, 0);
    
    D[s] = 0;
    priority_queue<Node, vector<Node>, cmp> h; // hàng đợi ưu tiên, sắp xếp theo dist[u] nhỏ nhất trước
    h.push({s, D[s]});
    
    while(!h.empty()) {
        Node x = h.top();
        h.pop();
        
        int u = x.u;
        if(P[u] == true) // Đỉnh u đã được chọn trước đó, bỏ qua
            continue;
            
        P[u] = true; // Đánh dấu đỉnh u đã được chọn
        for(auto e : E[u]) {
            int v = e.v;
            long long w = e.w; 
            
            if(D[v] > D[u] + w) {
                D[v] = D[u] + w;
                h.push({v, D[v]});
                trace[v] = u;
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Cũng giống như thuật toán Bellman-Ford, để tìm lại đường đi ngắn nhất từ SS về uu, ta sẽ bắt đầu từ đỉnh uu, sau đó truy vết theo mảng tracetrace ngược về SS.

vector<int> trace_path(vector<int> &trace, int S, int u) {
    if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi

    vector<int> path;
    while (u != -1) { // truy vết ngược từ u về S
        path.push_back(u);
        u = trace[u];
    }
    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S
    
    return path;
}

3. Thuật toán Floyd-Warshall

Thuật toán Floyd-Warshll dùng để giải quyết bài toán đường đi ngắn nhất mọi cặp đỉnh (All-pairs shortest path), đồ thị có thể có trọng số âm.

Bài toán

Cho đồ thị gồm NN đỉnh và một ma trận trọng số WW, trong đó ô (i,j)(i,j) cho biết rằng có một đường đi trực tiếp từ iji→j với trọng số là Wi,jWi,j. Yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị.

Giới hạn bài toán: 1N1001≤N≤100

Input: Dòng đầu tiên gồm số nguyên dương NNNN dòng tiếp theo, mỗi dòng gồm NN số biểu diễn một ma trận trong đó ô (i,j)(i,j) cho biết đường đi trực tiếp từ iji→j có trọng số là W[i,j]W[i,j].

Output: Ma trận kết quả trong đó giá trị ô (i,j)(i,j) là đường đi ngắn nhất từ iji→j.

Sample Input

5
0 4 2 1 6
7 0 1 2 4
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0

Sample Output

0 4 2 1 2
3 0 1 2 3
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0

Ý tưởng của thuật toán.

Ý tưởng của thuật toán này là: “Liệu chúng ta có thể chèn một đỉnh kk vào đường đi ngắn nhất giữa 2 đỉnh uu và vv?”.

  • Ví dụ như có một đường đi ngắn nhất từ 040→4 như sau: 012340→1→2→3→4. Vậy việc tính đường đi ngắn nhất từ 040→4 hoàn toàn có thể được chia thành tính đường đi ngắn nhất từ 020→2 sau đó cộng với đường đi ngắn nhất từ 242→4. Tương tự thế đường đi ngắn nhất từ 020→2 và 242→4 lại tiếp tực được phân hoạch thành những đường đi ngắn nhất khác đơn giản hơn và tối ưu hơn.

Ta nhận thấy có một cấu trúc đệ quy, chia nhỏ bài toán ở đây. Ý tưởng này cho phép chúng ta thực hiện một thuật toán mang hương vị quy hoạch động như sau:

  • Gọi D(u,v,k)D(u,v,k) là đường đi ngắn nhất, trong đó ta chỉ được đi qua kk đỉnh đầu tiên (có số thứ tự từ 00 đến k1k−1), ngoại trừ chính uu và vv. Ta có công thức truy hồi:

    • D(u,v,0)=Wu,vD(u,v,0)=Wu,v (không được dùng đỉnh nào ngoài chính u,vu,v).
    • D(u,u,k)=0D(u,u,k)=0
    • D(u,v,k)=D(u,v,k)= min của 2 trường hợp:

      • D(u,v,k1)D(u,v,k−1): ta không dùng đỉnh kk làm trung gian, giữ nguyên đường đi cũ.
      • D(u,k,k1)+D(k,v,k1)D(u,k,k−1)+D(k,v,k−1): ta dùng đỉnh kk làm trung gian, từ đường đi uvu→v thành đường đi ukvu→k→v.

Đến đây ta có thể sử dụng trực tiếp công thức quy hoạch động để cài đặt thuật toán. Tuy nhiên, để đảm bảo bộ nhớ, ta có thể tính các D(u,v,k)D(u,v,k) với kk lần lượt từ 11 đến NN, và khi cài đặt chỉ cần lưu lại D(u,v)D(u,v).

Cài đặt

  • Định nghĩa:

    • W[u,v]W[u,v] là giá trị đường đi trực tiếp từ uvu→v.
    • D[u,v]D[u,v] là giá trị đường đi ngắn nhất từ uvu→v.
    • trace[u,v]trace[u,v] là mảng truy vết đường đi ngắn nhất từ uvu→v
  • Đồ thị sẽ được lưu dưới dạng ma trận kề. Ban đầu sẽ khởi tạo mọi D[u,v]=W[u,v]D[u,v]=W[u,v] vì khi chưa tối ưu gì thì đường đi trực tiếp luôn là đường đi ngắn nhất.

    • trace[u,v]trace[u,v] sẽ khởi tạo bằng uu với mọi cặp u,vu,v.
    • Nếu không có cạnh nối giữa uu và vv, coi như W[u,v]=W[u,v]=∞ .
  • Thuật toán chỉ cần một vòng lặp xét mọi đỉnh kk như một đỉnh trung gian. Tiếp theo đến là 2 vòng lặp uuvv, có ý nghĩa thử chèn đỉnh kk vào giữa đường đi từ uu đến vv.

    • Nếu như D[u,v]D[u,v] được tối ưu bằng đỉnh kk, ta cập nhật thêm trace[u,v]=trace[k,v]trace[u,v]=trace[k,v]
  • Độ phức tạp của thuật toán là O(N3)O(N3).

Code: Thuật toán có thể được cài đặt rất dễ dàng chỉ với 3 vòng lặp:

void init_trace(vector<vector<int>> &trace) {
    int n = trace.size();
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            trace[u][v] = u;
        }
    }
}

void floydWarshall(int n, vector<vector<long long>> &w, vector<vector<long long>> &D, vector<vector<int>> &trace) {
    D = w;
    init_trace(trace); // nếu cần dò đường đi
    
    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (D[u][v] > D[u][k] + D[k][v]) {
                    D[u][v] = D[u][k] + D[k][v];
                    trace[u][v] = trace[k][v];
                }
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Giống như hai thuật toán Bellman-Ford và Dijkstra, để tìm đường đi từ uu đến vv, ta sẽ bắt đầu từ vv, truy ngược về uu theo mảng trace đã tìm được.

vector<int> trace_path(vector<vector<int>> &trace, int u, int v) {
    vector<int> path;
    while (v != u) { // truy vết ngược từ v về u
        path.push_back(v);
        v = trace[u][v];
    }
    path.push_back(u);
    
    reverse(path.begin(), path.end()); // cần reverse vì đường đi từ v ngược về u
    
    return path;
}

4. Lưu ý

  • Bảng so sánh các thuật toán được đề cập:
Bellman-Ford Dijkstra (cơ bản) Dijkstra (trên đồ thị thưa) Floyd-Warshall
Bài toán giải quyết Đường đi ngắn nhất một nguồn Đường đi ngắn nhất một nguồn Đường đi ngắn nhất một nguồn Đường đi ngắn nhất mọi cặp đỉnh
Độ phức tạp O(NM)O(N∗M) O(N2+M)O(N2+M) O(MlogN)O(MlogN) O(N3)O(N3)
Sử dụng được cho trọng số âm Không Không
Tìm được chu trình âm Không Không Không
  • Trong trường hợp có chu trình âm, thuật toán Floyd-Warshall có thể phải tính toán đến những giá trị rất nhỏ (về phía số âm), đủ để gây ra hiện tượng tràn số (thậm chí với NN tương đối nhỏ). Cần phải chú ý đặc biệt đến trường hợp này khi cài đặt.

    • Một cách thường dùng để giải quyết trường hợp này là gán D[u][v] = max(D[u][v], -INF) ngay sau mỗi lần tối ưu, chặn không cho D[u,v]D[u,v] xuống dưới hằng số âm vô tận.
  • Thuật toán Floyd-Warshall có thứ tự 3 vòng lặp là kuvk→u→v thay vì uvku→v→k (đỉnh trung gian phải được đặt ở vòng lặp ngoài cùng), đây là một nhầm lẫn tương đối phổ biến khi cài đặt.

  • Heap không phải là cấu trúc dữ liệu duy nhất có thể sử dụng khi cài đặt Dijkstra dành cho đồ thị thưa. Ta có thể sử dụng bất cứ cấu trúc dữ liệu nào hỗ trợ các thao tác “xóa khỏi tập hợp”“cập nhật phần tử trong tập hợp”“tìm phần tử nhỏ nhất trong tập hợp”. Thực tế cây nhị phân tìm kiếm (std::set trong C++) cũng là một lựa chọn phổ biến khi cài đặt thuật toán này.

  • Với đồ thị thưa, không có trọng số âm, thay vì sử dụng thuật toán Floyd, ta có thể chạy thuật toán Dijkstra cải tiến NN lần với NN đỉnh nguồn để tìm đường đi ngắn nhất giữa mọi cặp đỉnh, với độ phức tạp tốt hơn thuật toán Floyd:

    • Ta có độ phức tạp của hai thuật toán:
      • Dijkstra cải tiến, NN lần: O(NMlogN)O(N∗MlogN)
      • Floyd-Warshall: O(N3)O(N3)
    • Như vậy, để Dijkstra NN lần tốt hơn, ta cần có NMlogN<N3N∗MlogN<N3 suy ra M<N2/logNM<N2/logN (tương tự như so sánh giữa hai cách cài đặt thuật Dijkstra).

Bài tập vận dụng.

Thuật toán Bellman-Ford:

Thuật toán Dijkstra:

Thuật toán Floyd-Warshall: