एक निर्देशित ग्राफ प्रत्येक शीर्ष जोड़े के बीच भार के साथ प्रदान किया जाता है, और दो शीर्ष u और v भी प्रदान किए जाते हैं। हमारा कार्य शीर्ष u से शीर्ष v तक की सबसे छोटी दूरी ढूंढना है, ठीक k संख्या के किनारों के साथ।
इस समस्या को हल करने के लिए, हम शीर्ष u से शुरू करेंगे और सभी आसन्न शीर्षों पर जाएंगे और k मान का उपयोग करके k - 1 के रूप में आसन्न शीर्षों के लिए पुनरावृत्ति करेंगे।
इनपुट और आउटपुट
इनपुट: ग्राफ का लागत मैट्रिक्स। 0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 आउटपुट: सबसे छोटे पथ का भार 9 है
एल्गोरिदम
shortKEdgePath(u, v, edge)
इनपुट: शीर्ष u और v, और किनारों की संख्या।
आउटपुट: सबसे छोटे पथ की दूरी।
शुरू यदि edge = 0 और u = v, तो वापस करें 0 यदि edge = 1 और cost[u, v] ≠ ∞, तो वापस करें cost[u, v] यदि edge <= 0, तो वापस करें ∞ shortPath := ∞ सेट करें सभी शीर्ष i के लिए, करें यदि cost[u, i] ≠ ∞ और u ≠ i और v ≠ i, तो tempRes := shortKEdgePath(i, v, edge - 1) यदि tempRes ≠ ∞, तो shortPath = shortPath और (cost[u,i]+tempRes का न्यूनतम किया shortPath वापस करें अंत
उदाहरण
#include <iostream> #define NODE 4 #define INF INT_MAX using namespace std; int cost[NODE][NODE] = { {0, 10, 3, 2}, {INF, 0, INF, 7}, {INF, INF, 0, 6}, {INF, INF, INF, 0} }; int minimum(int a, int b) { return (a
आउटपुट
Weight of the shortest path is 9
