सटीक k किनारों के साथ स्रोत से गंतव्य तक संभावित पथ

परिचय

एक निर्देशित ग्राफ दिया गया है। दो अन्य शीर्ष u और v भी दिए गए हैं, u प्रारंभिक शीर्ष है, और v अंतिम शीर्ष है। हमारा कार्य शीर्ष u से v तक ठीक k किनारों वाले पथों की संख्या ढूंढना है। k का मान भी एल्गोरिदम में प्रदान किया गया है।

डायनामिक प्रोग्रामिंग का उपयोग करके, हमें एक 3D तालिका बनाने की आवश्यकता है, जहां पंक्ति u के मानों को इंगित करेगी, स्तंभ v के मानों को इंगित करेंगे और गहराई का उपयोग प्रारंभ से अंत तक किनारों की संख्या को ट्रैक करने के लिए किया जाएगा।

इनपुट और आउटपुट

इनपुट: ग्राफ का आसन्न मैट्रिक्स:
गंतव्य शीर्ष 3 है। K = 2
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
आउटपुट: 0 से 3 तक 2 किनारों के साथ 2 संभावित पथ हैं।

एल्गोरिदम

numberOfWalks(u, v, k)
इनपुट: प्रारंभ शीर्ष u, अंत शीर्ष v, किनारों की संख्या k
आउटपुट: k किनारों के साथ संभावित पथों की संख्या

Begin
    क्रम (n x n x k+1) का 3D सरणी count परिभाषित करें
    // n शीर्षों की संख्या है
    edge के लिए रेंज 0 से k तक, करें
        i के लिए रेंज 0 से n-1 तक, करें
            j के लिए रेंज 0 से 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 के लिए रेंज 0 से n तक, और i के साथ आसन्न करें
                        count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1]
                    done
                done
            done
        done
    done
    count[u, v, k] लौटाएं
End

उदाहरण (C++ कोड)

#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; // प्रारंभ में सभी मान 0 हैं
                if (edge == 0 && i == j)
                    // जब e 0 हो और iवें और jवें नोड समान हों, केवल एक पथ
                    count[i][j][edge] = 1;
                if (edge == 1 && graph[i][j])
                    // जब e 0 हो और (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.