सभी जोड़े सबसे छोटे रास्ते

सभी जोड़ी सबसे छोटे पथ एल्गोरिदम को फ़्लॉइड-वारशॉल एल्गोरिदम के रूप में भी जाना जाता है जिसका उपयोग किसी दिए गए भारित ग्राफ से सभी जोड़ी सबसे छोटी पथ समस्या को खोजने के लिए किया जाता है। इस एल्गोरिथम के परिणामस्वरूप, यह एक मैट्रिक्स उत्पन्न करेगा, जो ग्राफ़ में किसी भी नोड से अन्य सभी नोड्स के लिए न्यूनतम दूरी का प्रतिनिधित्व करेगा।

सबसे पहले आउटपुट मैट्रिक्स ग्राफ के दिए गए लागत मैट्रिक्स के समान है। उसके बाद आउटपुट मैट्रिक्स को सभी शीर्षों k के साथ मध्यवर्ती शीर्ष के रूप में अद्यतन किया जाएगा।

इस एल्गोरिथम की समय जटिलता O(V3) है, यहाँ V ग्राफ़ में शीर्षों की संख्या है।

इनपुट - ग्राफ़ का लागत मैट्रिक्स।

0 3 6 3 0 2 1 6 2 0 1 4 2 1 1 0 2 ∞ 4∞ 4 2 0 2 1∞ ∞ 2 ∞ 2 0 1∞ 4 1 1 0

आउटपुट - सभी जोड़ी सबसे छोटे पथ का मैट्रिक्स।

0 3 4 5 6 7 73 0 2 1 3 4 44 2 0 1 3 2 35 1 1 0 2 3 36 3 3 2 0 2 17 4 2 3 2 0 17 4 3 3 1 1 0

एल्गोरिदम

floydWarshal(लागत)

इनपुट − दिए गए ग्राफ़ का लागत मैट्रिक्स।

आउटपुट - किसी भी शीर्ष से किसी भी शीर्ष के बीच सबसे छोटे पथ के लिए मैट्रिक्स।

k के लिए शुरू करें:=0 से n, i के लिए करें:=0 से n, j के लिए करें:=0 से n, यदि लागत [i, k] + लागत [k, j] <लागत [i, j], फिर लागत[i,j] :=लागत[i,k] + लागत[k,j] किया गया हो गया वर्तमान लागत मैट्रिक्स प्रदर्शित करेंअंत

उदाहरण

#include#include
#define NODE 7#define INF 999 यूज़िंग नेमस्पेस एसटीडी;//ग्रैफिंट कॉस्टमैट का कॉस्ट मैट्रिक्स [NODE][NODE] ={ {0, 3, 6, INF, INF , INF, INF}, {3, 0, 2, 1, INF, INF, INF}, {6, 2, 0, 1, 4, 2, INF}, {INF, 1, 1, 0, 2, INF , 4}, {INF, INF, 4, 2, 0, 2, 1}, {INF, INF, 2, INF, 2, 0, 1}, {INF, INF, INF, 4, 1, 1, 0 }};Void floydWarshal(){ int cost[NODE][NODE]; // (int i =0; i 
आउटपुट
 
मैट्रिक्स:0 3 5 4 6 7 73 0 2 1 3 4 45 2 0 1 3 2 34 1 1 0 2 3 36 3 3 2 0 2 17 4 2 3 2 0 17 4 3 3 1 1 0