Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

फ्लोयड वारशाल एल्गोरिथम

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

फ्लोयड वारशाल एल्गोरिथम

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

इस एल्गोरिथम की समय जटिलता O(V^3) है, जहां 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 }};शून्य फ्लोयडवारशल () {अंतर लागत [नोड] [नोड]; // (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
  1. फोर्ड फुलकर्सन एल्गोरिथम

    फोर्ड-फुलकर्सन एल्गोरिथम का उपयोग किसी दिए गए ग्राफ में प्रारंभ शीर्ष से सिंक शीर्ष तक अधिकतम प्रवाह का पता लगाने के लिए किया जाता है। इस ग्राफ में हर किनारे की क्षमता है। स्रोत और सिंक नाम के दो शीर्ष दिए गए हैं। स्रोत शीर्ष में सभी बाहरी किनारे हैं, कोई अंदरूनी किनारा नहीं है, और सिंक में सभी अंदर

  1. एल्गोरिथम विशिष्टता-डेटा संरचना में परिचय

    एक एल्गोरिदम को निर्देशों के एक सीमित सेट के रूप में परिभाषित किया जाता है, जिसका पालन किया जाता है, तो एक विशेष कार्य करता है। सभी एल्गोरिदम को निम्नलिखित मानदंडों को पूरा करना चाहिए इनपुट एक एल्गोरिथम में शून्य या अधिक इनपुट होते हैं, वस्तुओं के निर्दिष्ट सेट से लिए या एकत्र किए जाते हैं। आउटपुट

  1. मैट्रिक्स गुणन एल्गोरिथ्म

    इस भाग में हम देखेंगे कि दो आव्यूहों को कैसे गुणा किया जाता है। मैट्रिक्स गुणन केवल तभी किया जा सकता है, जब यह इस शर्त को पूरा करता हो। मान लीजिए कि दो मैट्रिक्स ए और बी हैं, और उनके आयाम ए (एम एक्स एन) और बी (पी एक्स क्यू) हैं, तो परिणामी मैट्रिक्स पाया जा सकता है यदि और केवल अगर एन =पी। तब परिणामी