C++-এ গ্রাফে سورস থেকে K-ও অধিক দৈর্ঘ্যের পাথ আছে কিনা যাচাই

কনসেপ্ট

একটি গ্রাফ, সোর্স ভার্টেক্স এবং একটি সংখ্যা k দেওয়া আছে। সোর্স থেকে শুরু করে যেকোনো ভের্টেক্সে শেষ হওয়া সিম্পল পাথ (সাইকেল ছাড়া) আছে কিনা যেটির দৈর্ঘ্য k-র চেয়ে বড়।

ইনপুট: Source s=0, k=64 -> আউটপুট: True (পাথ দৈর্ঘ্য ৬৮)। k=70 -> আউটপুট: False (সর্বোচ্চ পাথ দৈর্ঘ্য ৬৯)।

পদ্ধতি

ব্যাকট্র্যাকিং (Backtracking) ব্যবহার করুন। সোর্স থেকে সব পাথ এক্সপ্লোর করুন। করেন্ট ডিস্ট্যান্স ট্র্যাক করুন। ডিস্ট্যান্স > k হলে true ফেরত দিন। পাথ সিম্পল রাখতে ভিজিটেড অ্যারে ব্যবহার করুন। ছোট এজ বড় পাথ তৈরি করতে পারে তাই গ্রিডি কাজ করবে না।

উদাহরণ (C++ কোড)

// প্রোগ্রাম: k-ও অধিক ওজনের সিম্পল পাথ আছে কিনা
#include <bits/stdc++.h>
using namespace std;
typedef pair iPair;

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

Graph::Graph(int V1) { this->V1 = V1; adj1 = new list[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));
}

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

bool Graph::pathMoreThanKUtil(int src1, int k, vector& path1) {
    if (k <= 0) return true;
    for (auto i = adj1[src1].begin(); i != adj1[src1].end(); ++i) {
        int v1 = (*i).first, 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;
}

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, 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;
}

আউটপুট

No Yes