Kiểm tra xem có đường đi dài hơn k từ nguồn trong đồ thị trong C++

Khái niệm

Cho đồ thị, đỉnh nguồn và số k (độ dài đường đi giữa nguồn và đích), xác định xem có đường đi đơn giản (không chu trình) bắt đầu từ nguồn và kết thúc tại bất kỳ đỉnh nào khác. Đồ thị như hình:

Đầu vào

Source s = 0, k = 64

Đầu ra

True

Tồn tại đường đi đơn giản 0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4, tổng khoảng cách 68 > 64.

Đầu vào

Source s = 0, k = 70

Đầu ra

False

Đường đi đơn giản dài nhất có độ dài 69, nên kết quả false cho mọi k > 69.

Phương pháp

Lưu ý: chỉ dùng BFS/DFS và chọn cạnh dài nhất mỗi bước không hoạt động vì cạnh ngắn hơn có thể dẫn đến đường đi dài hơn nhờ các cạnh trọng số lớn hơn nối tiếp.

Ý tưởng: sử dụng Backtracking. Bắt đầu từ nguồn, duyệt tất cả đường đi từ đỉnh hiện tại. Theo dõi khoảng cách hiện tại từ nguồn. Nếu khoảng cách > k, trả về true. Nếu đường đi không tạo ra khoảng cách > k, quay lui (backtrack).

Để đảm bảo đường đi đơn giản và không lặp chu trình: theo dõi các đỉnh trong đường đi hiện tại bằng mảng. Khi thêm đỉnh, kiểm tra xem đã tồn tại trong đường đi hiện tại chưa. Nếu có, bỏ qua cạnh đó.

Ví dụ

// Chương trình tìm đường đi đơn giản có trọng số lớn hơn k
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> iPair;

class Graph{
    int V1;
    list< pair<int, int>> *adj1;
    bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
    Graph(int V1);
    void addEdge(int u1, int v1, int w1);
    bool pathMoreThanK(int src1, int k);
};

bool Graph::pathMoreThanK(int src1, int k){
    vector<bool> path1(V1, false);
    path1[src1] = 1;
    return pathMoreThanKUtil(src1, k, path1);
}

bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
    if (k <= 0) return true;
    list<iPair>::iterator i;
    for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
        int v1 = (*i).first;
        int w1 = (*i).second;
        if (path1[v1] == true) continue;
        if (w1 >= k) return true;
        path1[v1] = true;
        if (pathMoreThanKUtil(v1, k-w1, path1)) return true;
        path1[v1] = false;
    }
    return false;
}

Graph::Graph(int V1){
    this->V1 = V1;
    adj1 = new list<iPair> [V1];
}

void Graph::addEdge(int u1, int v1, int w1){
    adj1[u1].push_back(make_pair(v1, w1));
    adj1[v1].push_back(make_pair(u1, w1));
}

int main(){
    int V1 = 9;
    Graph g(V1);
    g.addEdge(0, 1, 5);
    g.addEdge(0, 7, 9);
    g.addEdge(1, 2, 9);
    g.addEdge(1, 7, 12);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 8, 3);
    g.addEdge(2, 5, 10);
    g.addEdge(3, 4, 10);
    g.addEdge(3, 5, 15);
    g.addEdge(4, 5, 11);
    g.addEdge(5, 6, 3);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 7);
    g.addEdge(7, 8, 8);
    int src1 = 0;
    int k = 70;
    g.pathMoreThanK(src1, k)? cout << "Yes\n" : cout << "No\n";
    k = 68;
    g.pathMoreThanK(src1, k)? cout << "Yes\n" : cout << "No\n";
    return 0;
}

Đầu ra

No Yes