फ्लोयड-वारशेल एलगोरिदम

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



इस एल्गोरिथ्म को एक साथ 1962 में रॉबर्ट फ्लॉयड और स्टीफन वॉर्सहॉल के लेखों में प्रकाशित किया गया था, हालांकि बर्नार्ड रॉय ने 1959 में लगभग एक ही एल्गोरिथ्म प्रकाशित किया था, लेकिन यह किसी का ध्यान नहीं गया।

टिप्पणी

यदि ग्राफ़ में नकारात्मक भार वाले किनारों को शामिल नहीं किया गया है, तो इस समस्या को हल करने के लिए, आप एक वर्टेक्स से अन्य सभी के लिए सबसे छोटा रास्ता खोजने के लिए डायजेस्ट्रा एल्गोरिथम का उपयोग कर सकते हैं, इसे प्रत्येक शीर्ष पर चला रहे हैं। इस तरह के एल्गोरिथ्म का संचालन समय उस डेटा के प्रकार पर निर्भर करता है जिसका उपयोग हम दिक्जस्ट्रा एल्गोरिथ्म के लिए करेंगे, यह या तो एक साधारण प्राथमिकता कतार या बाइनरी या फाइबोनैचि हीप हो सकता है , क्रमशः ऑपरेटिंग समय O (V ³ ) से O (V * E) तक भिन्न होगा * log (V)), जहां V वर्टिस की संख्या है, और E किनारे है। ( "ओह" महान है )।



यदि नकारात्मक वजन के साथ किनारे हैं, तो आप बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग कर सकते हैं। लेकिन ग्राफ़ के सभी कोने पर चलने वाला यह एल्गोरिथ्म धीमा है, इसका ऑपरेटिंग समय O (V ² * E) है, और बहुत "मोटे" ग्राफ़ में यह O (V ⁴ ) है।

गतिशील प्रोग्रामिंग

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



1. कार्य को छोटे उप-प्रकारों में विभाजित करना।

2. उपकेंद्रों के लिए इष्टतम समाधान ढूँढना पुनरावर्ती है।

3. मूल समस्या के समाधान के निर्माण के लिए उपकेंद्रों के प्राप्त समाधान का उपयोग करना।



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

सबसे छोटी पथ संरचना

एल्गोरिदम एक ग्राफ के सबसे छोटे मार्ग के दो गुणों पर आधारित है। पहली:



वहाँ सबसे छोटा रास्ता p _1k = (v ₁ , v ₂ , ..., v _k ) है, जो शीर्ष ₁ v से शीर्ष v v तक है, साथ ही इसके उपपथ p '(v _i , v _{i + 1} , ..., v _j , जबकि) 1 <= i <= j <= k कार्य करता है।

यदि p v ₁ से v _k तक सबसे छोटा रास्ता है, तो p 'भी शीर्ष v से v _j तक का सबसे छोटा मार्ग है

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



दूसरी संपत्ति एल्गोरिदम का आधार है। हम एक ग्राफ G को कोने के साथ मानते हैं {v ₁ , v ₂ , ..., v _n } को 1 से n तक और पथ p _ij को v _i से v _j तक एक निश्चित सेट के माध्यम से गुजरते हुए अनुक्रमणिका k द्वारा बाउंड किया गया।



यही है, यदि k = 0 है, तो हम एक दूसरे को कोने के प्रत्यक्ष कनेक्शन पर विचार करते हैं, क्योंकि अनुमत मध्यवर्ती कोने का सेट जल्दी शून्य है। यदि k = 1 - हम क वर्टिका v ₁ से गुजरने वाले रास्तों को k = 2 के लिए मानते हैं, तो वर्धमान {v ₁ , v ₂ } के माध्यम से, k = 3 - {v ₁ , v ₃ , v ₃ } और इसी तरह।



उदाहरण के लिए, हमारे पास ऐसा एक ग्राफ (बाएं) और k = 1 है, अर्थात केवल नोड "1" को मध्यवर्ती नोड्स के रूप में अनुमति दी गई है। इस ग्राफ़ में, k = 1 के लिए, कोई पथ p _{43 नहीं है} , लेकिन k = 2 के लिए, तो आप "4" से "3" तक "2" या "1" और "2" के माध्यम से प्राप्त कर सकते हैं।



स्वीकृत इंटरमीडिएट कोने {1..k-1} लागत d _{ij के} साथ सबसे छोटा रास्ता p _ij पर विचार करें। अब हम सेट को kth एलिमेंट तक बढ़ाते हैं, ताकि अनुमत वर्टिकल का सेट {1..k} हो जाए। इस विस्तार के साथ, 2 परिणाम संभव हैं:



केस 1. तत्व k को सबसे कम पथ p _ij में शामिल नहीं किया गया है, अर्थात, एक अतिरिक्त शीर्ष के अतिरिक्त से हमने कुछ भी नहीं जीता और कुछ भी नहीं बदला, जिसका अर्थ है कि सबसे कम पथ d ^k _ij की लागत क्रमशः नहीं बदली गई है

d ^k _ij = d ^k-1 _ij - जब तक k बढ़ता नहीं है तब तक मान लें।

केस 2. तत्व k सबसे छोटा पथ p _{ij में} प्रवेश करता है, अर्थात, अनुमत पथ में एक नया शीर्ष जोड़ने के बाद, सबसे छोटा पथ बदल गया है और अब वर्टेक्स v _k से गुजरता है। नया रास्ता कितना मिलेगा?



नए सबसे छोटे पथ को वर्टेक्स v _k द्वारा p _ik और p _kj में विभाजित किया गया है, हम पहली संपत्ति का उपयोग करते हैं, इसके अनुसार, p _ik और p _kj क्रमशः v _i से v _k और v _k से v _j तक के सबसे छोटे पथ हैं। इतना



d ^k _ij = d ^k _ik + d ^k _kj



और चूंकि इन रास्तों में k या तो अंतिम या प्रारंभिक नोड है, यह मध्यवर्ती नोड्स के सेट में शामिल नहीं है, इसलिए आप इसे इससे निकाल सकते हैं:

d ^k _ij = d ^k-1 _ik + d ^k-1 _kj

एल्गोरिथ्म

आइए दोनों मामलों में d ^k _ij का मान देखें - सही है! दोनों मामलों में यह k-1 के लिए d मानों का योग है, जिसका अर्थ है कि d के लिए प्रारंभिक (k = 0) मान होने के बाद, हम बाद के सभी k मानों के लिए d की गणना कर सकते हैं। और हम k = 0 के लिए d मानों को जानते हैं, यह ग्राफ के किनारों का भार / लागत है, अर्थात्, मध्यवर्ती नोड्स के बिना यौगिक।



K = n (n वर्टिकल की संख्या है) के लिए हम सभी जोड़ के लिए d का इष्टतम मान प्राप्त करते हैं।



K-1 से k तक बढ़ते समय, हम d ^k _{ik के} लिए क्या मूल्य रखते हैं? केस 1 और 2 के न्यूनतम मूल्यों से, यानी हम देखते हैं कि अतिरिक्त पथ के साथ पुराना पथ या पथ सस्ता है या नहीं।

छद्म कोड

अंत में, एल्गोरिथ्म ही। हम ग्राफ प्रतिनिधित्व का उपयोग आसन्न के मैट्रिक्स के रूप में करते हैं।







जैसा कि आप देख सकते हैं, एल्गोरिथ्म बहुत सरल है - सबसे पहले कम से कम दूरी मैट्रिक्स D ⁰ को आरंभीकृत किया जाता है, शुरू में यह आसन्न मैट्रिक्स के साथ मेल खाता है, चक्र में हम k का मान बढ़ाते हैं और दूरी मैट्रिक्स की पुनर्गणना करते हैं, ^{0 से} हमें D ¹ - D ² - D ² और इसी से k पर k मिल जाता है। = एन।



यह माना जाता है कि यदि किसी भी दो कोने के बीच कोई किनारा नहीं है, तो आसन्न मैट्रिक्स में कुछ बड़ी संख्या लिखी गई थी (बड़ी पर्याप्त है ताकि यह इस ग्राफ में किसी भी पथ की लंबाई से अधिक हो); तब यह बढ़त हमेशा लेने के लिए हानिकारक होगी, और एल्गोरिथ्म सही ढंग से काम करेगा। हालांकि, यदि विशेष उपाय नहीं किए जाते हैं, तो अगर किनारों के ग्राफ में एक नकारात्मक वजन है, तो फॉर्म ∞-1, ∞-2, आदि की संख्या, जो निश्चित रूप से, इसका मतलब अभी भी इसी के बीच है। चोटियों का कोई रास्ता नहीं है। इसलिए, यदि ग्राफ़ में नकारात्मक किनारे हैं, तो फ्लॉयड एल्गोरिदम लिखना बेहतर है ताकि यह उन राज्यों से संक्रमण न करे जिसमें पहले से ही "कोई रास्ता नहीं" है

उदाहरण

मैट्रिक्स का पहला पुनर्गणना - एक मूल्य में परिवर्तन, वर्टिकल के अनुमत वर्टेक्स के विस्तार के कारण "1" करने के लिए, हम एक सस्ते तरीके का उपयोग करके "4" से "2" तक प्राप्त करने में सक्षम थे।



d ^k _ij = min (d ^k-1 _ij ; d ^k-1 _ik + d ^k-1 _kj )



d ¹ ₄₂ = मिनट (d ⁰ ₄₂ , d ⁰ ₄₁ + d ⁰ ₁₂ )



d ¹ ₄₂ = मिनट (4, -1)



दूसरा पुनरावृत्ति, पी _{43 के} लिए बेहतर मूल्य







परिणाम







यहां और वहां आप एप्लेट के साथ खेल सकते हैं और देख सकते हैं कि एल्गोरिथ्म कैसे काम करता है।

ऑपरेटिंग समय और मेमोरी उपयोग का विश्लेषण

एल्गोरिथ्म को मैट्रिसेस को स्टोर करने के लिए O (n ³ ) मेमोरी की आवश्यकता होती है। हालांकि, मैट्रिसेस की संख्या को आसानी से दो तक घटाया जा सकता है, हर बार एक अनावश्यक मैट्रिक्स को फिर से लिखना या यहां तक ​​कि डी _केजे से इंडेक्स के को हटाकर एक दो-आयामी मैट्रिक्स पर जाना होगा। सबसे अधिक उपयोग किया जाने वाला सबसे अच्छा विकल्प सीधे आसन्न मैट्रिक्स पर लिखना है, फिर हमें अतिरिक्त मेमोरी की आवश्यकता नहीं है, हालांकि यदि हम तुरंत मूल मैट्रिक्स को फिर से लिखते हैं, तो हमें एल्गोरिथ्म की शुद्धता को अतिरिक्त रूप से दिखाने की आवश्यकता है, क्योंकि शास्त्रीय शैक्षणिक प्रमाण केवल मामले के लिए सही है जब पिछले पुनरावृत्ति का मैट्रिक्स। बदलता नहीं है।



ऑपरेटिंग समय के लिए - तीन नेस्टेड चक्र 1 से n - n (n ³ ) तक।

नकारात्मक चक्रों का मामला

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



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

रास्ते का पुनर्निर्माण

दूरी मैट्रिक्स हमें किसी भी जोड़ी के लिए सबसे छोटी (सबसे सस्ती) दूरी दिखाएगा, लेकिन आप मार्ग को कैसे जानते हैं? बहुत आसान है, जब डी ^के _{आईजे की} गणना करते हैं, तो एक को j ^के _{आईजे की} गणना करने की भी आवश्यकता होती है। π ^k _ij इस मामले में पूर्ववर्ती वर्टिकल वर्टिज {1..k} के सेट के साथ v _i से पथ पर v v का पूर्ववर्ती है।



मैं इसे बस यहीं छोड़ दूंगा, बाकी सभी लोग खुद इसके बारे में सोच सकते हैं

आवेदन

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



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











<sub>यह सब, बहुत लिखा नहीं है, इसलिए यदि आप त्रुटियों, विसंगतियों, गलतफहमी आदि को इंगित करते हैं, तो मैं आभारी रहूंगा, मुझे अभी भी इस पाठ की आवश्यकता होगी :)



धन्यवाद रुस्तम 'y और mastersobg ' सुधार के लिए</sub>