নির্দিষ্ট k এজ সহ পথ গণনা (Possible walks from a source to a destination with exactly k edges)

একটি ডায়렉্টেড গ্রাফ দেওয়া আছে। আর দুটি ভার্টেক্স u এবং v দেওয়া আছে, u হল শুরু নোড, এবং v হল শেষ নোড। আমাদের কাজ u থেকে v পর্যন্ত ঠিক kটি এজ দিয়ে যেতে পারা পথের সংখ্যা বের করা। k-এর মানও অ্যালগরিদমে দেওয়া থাকে।

ডাইনামিক প্রোগ্রামিং ব্যবহার করে, আমাদের একটি ৩D টেবিল তৈরি করতে হবে, যেখানে রো u-এর মান নির্দেশ করবে, কলাম v-এর মান নির্দেশ করবে এবং ডেপথ শুরু থেকে শেষ পর্যন্ত এজের সংখ্যা ট্র্যাক করবে।

ইনপুট এবং আউটপুট

ইনপুট: গ্রাফের অ্যাকোডেন্সি ম্যাট্রিক্স: গন্তব্য ভার্টেক্স ৩। K = 2 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 আউটপুট: ০ থেকে ৩ পর্যন্ত ২টি এজ দিয়ে ২টি সম্ভাব্য পথ আছে।

অ্যালগরিদম

numberOdWalks(u, v, k)

ইনপুট: শুরু ভার্টেক্স u, শেষ ভার্টেক্স v, এজের সংখ্যা k।

আউটপুট: k এজ দিয়ে সম্ভাব্য পথের সংখ্যা।

শুরু 
  count নামক ৩D অ্যারে সংজ্ঞায়িত করুন আকার (n x n x k+1) 
  //n হল ভার্টেক্সের সংখ্যা 
  edge ০ থেকে k পর্যন্ত রেঞ্জে, করুন 
    i ০ থেকে n-1 পর্যন্ত রেঞ্জে, করুন 
      j ০ থেকে n-1 পর্যন্ত রেঞ্জে, করুন 
        count[i, j, edge] := 0 
        যদি edge = 0 এবং i = j, তবে 
          count[i, j, edge] := 1 
        যদি edge = 1 এবং (i, j) সংযুক্ত থাকে, তবে 
          count[i, j, edge] := 1 
        যদি edge > 1, তবে 
          a ০ থেকে n রেঞ্জে, এবং i-এর সাথে সন্নিহিত করুন 
            count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1] 
          শেষ 
        শেষ 
      শেষ 
    শেষ 
  শেষ 
  count[u, v, k] ফেরত দিন 
শেষ

উদাহরণ

#include <iostream> #define NODE 7 using namespace std; int graph[NODE][NODE] = {   {0, 1, 1, 1},   {0, 0, 0, 1},   {0, 0, 0, 1},   {0, 0, 0, 0} }; int numberOfWalks(int u, int v, int k) {   int count[NODE][NODE][k+1];   for (int edge = 0; edge <= k; edge++) {     //k এজ (0..k) জন্য     for (int i = 0; i < NODE; i++) {       for (int j = 0; j < NODE; j++) {         count[i][j][edge] = 0;         //প্রাথমিকভাবে সব মান ০         if (edge == 0 && i == j)           //যখন e ০ এবং i-তম এবং j-তম নোড একই, শুধু একটি পথ         count[i][j][edge] = 1;         if (edge == 1 && graph[i][j])           //যখন e ০ এবং সরাসরি পথ (i থেকে j), একটি পথ         count[i][j][edge] = 1;         if (edge >1) {           //একটির বেশি এজ জন্য           for (int a = 0; a < NODE; a++)           // সোর্স i-এর সন্নিহিত       if (graph[i][a])             count[i][j][edge] += count[a][j][edge-1];         }       }     }   }   return count[u][v][k]; } int main() {   int u = 0, v = 3, k = 2;   cout << "There are "<< numberOfWalks(u, v, k)<<" Possible Walks, from ";   cout <<u<<" to "<<v<<" with "<<k<<" edges."; }

আউটপুট

There are 2 Possible Walks, from 0 to 3 with 2 edges.