ঠিক k প্রান্ত সহ একটি উৎস থেকে গন্তব্যে সম্ভাব্য হাঁটা

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

ডায়নামিক প্রোগ্রামিং ব্যবহার করে, আমাদের একটি 3D টেবিল তৈরি করতে হবে, যেখানে সারিটি u-এর মান নির্দেশ করবে, কলামগুলি v মান নির্দেশ করবে এবং শুরু থেকে শেষ পর্যন্ত প্রান্তের সংখ্যা ট্র্যাক করতে গভীরতা ব্যবহার করা হবে৷

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

Input:
The adjacency matrix of the graph: The destination vertex is 3. K = 2
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
Output:
There are 2 Possible Walks, from 0 to 3 with 2 edges.

অ্যালগরিদম

numberOdWalks(u, v, k)

ইনপুট: শুরুর শীর্ষবিন্দু u, শেষ শীর্ষবিন্দু v, প্রান্তের সংখ্যা k।

আউটপুট: k প্রান্ত সহ সম্ভাব্য হাঁটার সংখ্যা।

Begin
   define 3D array count of order (n x n x k+1)    //n is number of vertices
   for edge in range 0 to k, do
      for i in range 0 to n-1, do
         for j in range 0 to n-1, do
            count[i, j, edge] := 0
            if edge = 0 and i = j, then
               count[i, j, edge] := 1
            if edge = 1 and (i, j) is connected, then
               count[i, j, edge] := 1
            if edge > 1, then
               for a in range 0 to n, and adjacent with i do
                  count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1]
               done
         done
      done
   done
   return count[u, v, k]
End

উদাহরণ

#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++) {           //for k edges (0..k)
      for (int i = 0; i < NODE; i++) {
         for (int j = 0; j < NODE; j++) {
            count[i][j][edge] = 0;               //initially all values are 0

            if (edge == 0 && i == j)            //when e is 0 and ith and jth node are same, only one path
               count[i][j][edge] = 1;
            if (edge == 1 && graph[i][j])           //when e is 0 and direct path from (i to j), one path
               count[i][j][edge] = 1;
            if (edge >1) {                           //for more than one edges
               for (int a = 0; a < NODE; a++)         // adjacent of source 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.