🔐 👶🏾 🥨 सबसे छोटे के लिए मायने रखता है: फोर्ड और बेलमैन या यह कैसे समझें कि आप असीम रूप से दूर अतीत में हैं 👩🏾‍⚕️ ✋🏾 👨‍⚕️

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

समस्या का बयान

समस्या में, एक भारित ग्राफ माना जाता है - अर्थात्, एक निश्चित संख्या से जुड़े प्रत्येक किनारे के साथ एक ग्राफ, जिसे उसका वजन कहा जाता है। किनारे के वजन का शीर्ष u से वर्टेक्स v तक होता है जिसे वजन [u, v] द्वारा दर्शाया जाएगा।
वर्टेक्स यू से वर्टेक्स वी तक का रास्ता खोजना आवश्यक है, जिसके किनारों का भार न्यूनतम है। वेट के इस योग को वर्टेक्स यू से वर्टेक्स v तक की दूरी कहा जाएगा और डिस्ट [यू, वी] द्वारा निरूपित किया जाएगा।

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

चलो कुछ सरल के साथ आते हैं

कुछ किनारे (v, w) पर विचार करें। इसके अंत की दूरियों के बारे में हम क्या कह सकते हैं? जाहिर है, डिस्ट [यू, डब्ल्यू] u डिस्ट [यू, वी] + वेट [वी, डब्ल्यू]।

सबूत

डिस्ट यू [यू, वी] = के। इसका मतलब है कि यू से वी के वजन का एक रास्ता है। इस मार्ग में किनारे (v, w) को जोड़ें। हम वजन + के [यू, डब्ल्यू] को तौलने के लिए यू से रास्ता प्राप्त करते हैं। चूँकि u से w की दूरी, u और v को जोड़ने वाले सभी रास्तों की लंबाई से कम से कम है, dist [u, w] v K + वजन [v, w]

आइए, इसे चलने दें। प्रारंभ में, दूरी को केवल प्रारंभिक शीर्ष पर जाना जाता है - यह 0. है समय के प्रत्येक क्षण में, हम कुछ किनारे के लिए संपत्ति की पूर्ति की जांच कर सकते हैं और यदि इसका उल्लंघन किया जाता है, तो किनारे के अंतिम शीर्ष तक दूरी के मौजूदा अनुमान में सुधार करें। इस प्रक्रिया को विश्राम कहा जाता है।

शब्द कुछ भी नहीं हैं, मुझे कोड दिखाओ!

फोर्ड और बेलमैन एल्गोरिथ्म

कोड मानता है कि ग्राफ वेक्टर में संग्रहित है <वेक्टर <जोड़ी <int, int >>> किनारों, जहां किनारों [v] सभी किनारों का वेक्टर है, जो शीर्ष v से निकलता है। किनारे के किनारों में [v] [i], पहला क्षेत्र किनारे का अंतिम शीर्ष है, और दूसरा इसका वजन है। INF एक स्थिरांक है जिसे किसी भी परिणामी दूरी से बड़ा माना जाता है। एक ज्ञात पथ की अनुपस्थिति को दर्शाता है।

void ford_bellman(int start) { //  for (int i = 0; i < (int)edges.size(); ++i) { dist[i] = INF; } dist[start] = 0; // V     for (int iter = 0; iter < (int)edges.size(); ++iter) { //    for (int v = 0; v < (int)edges.size(); ++v) { //    for (int i = 0; i < (int)edges[v].size(); ++i) { //   if (dist[edges[v][i].first] > dist[v] + edges[v][i].second) { //   dist[edges[v][i].first] = dist[v] + edges[v][i].second; } } } } }

एक एल्गोरिथ्म को कितने संसाधनों की आवश्यकता होती है?

ग्राफ़ और प्रतिक्रिया में दिए गए मानों के अलावा, हम केवल निरंतर मात्रा में मेमोरी संग्रहीत करते हैं, इसलिए, एल्गोरिथ्म द्वारा आवश्यक मेमोरी की मात्रा O (1) + <ग्राफ़ को संग्रहीत करने के लिए स्मृति है और प्रतिक्रिया> = O (V + E) = O (E)।
प्रत्येक पसली का विश्राम एक निरंतर मात्रा में कार्रवाई करता है। कुल पसलियों - ई, सभी पसलियों का विश्राम V समय पर किया जाता है। इस प्रकार, एल्गोरिथ्म का समय जटिलता O (VE) है।

क्या होगा अगर मैं एक पेडेंट हूं?

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

आधार: k = 0 स्पष्ट है, प्रारंभिक शिखर से इसका मार्ग सही तरीके से पाया जाता है
धारणा: सभी चक्करों के लिए k पुनरावृत्तियों के बाद v जिसमें k किनारों से अधिक नहीं के साथ एक छोटा रास्ता है, dist [v] प्रारंभिक शीर्ष से v तक की दूरी के बराबर है
चरण: कुछ शीर्ष w पर विचार करें जिसमें k + 1 किनारों से मिलकर एक छोटा रास्ता है।
- हम यू से डब्ल्यू के रूप में मार्ग में penultimate vertex को निरूपित करते हैं।
- V के लिए k vertices का सबसे छोटा रास्ता मौजूद है (उदाहरण के लिए, w का सबसे छोटा रास्ता)।
- इसलिए, पिछले पुनरावृत्ति में सबसे छोटा रास्ता v पाया गया। K + 1 पुनरावृत्ति पर किनारे (v, w) को शिथिल करने के बाद, हम दूरी के सही मूल्य को वर्टेक्स w तक प्राप्त करते हैं।
- ध्यान दें कि कुछ अन्य किनारे की छूट के दौरान, हम सही दूरी से छोटा मान नहीं पा सकते हैं, क्योंकि किनारे की प्रत्येक छूट (x, w) प्रारंभिक शीर्ष से पथ की संगत लंबाई से एक पथ से जुड़ी हो सकती है।

लेकिन समय यात्रा के बारे में क्या?

प्रमाण में, यह व्यर्थ नहीं था कि आरक्षण किया गया था - सभी मौजूदा सबसे छोटे रास्ते खोजे जाते हैं। ऐसी स्थिति है जिसमें यू से वी तक का रास्ता है, लेकिन यू से वी तक कोई सबसे छोटा रास्ता नहीं है - उदाहरण के लिए, यदि ये दोनों कोने नकारात्मक वजन के चक्र में प्रवेश करते हैं। यह मामले के गणितीय समकक्ष है जब कोने के बीच के संक्रमण पोर्टल होते हैं, और जो अतीत और भविष्य दोनों में फेंक सकते हैं। नकारात्मक वजन के एक चक्र की उपस्थिति का मतलब है कि इसके माध्यम से घूमने की सही संख्या के बाद, आप अतीत में जहां तक चाहें, हो सकते हैं।
फोर्ड-बेलमैन एल्गोरिथ्म भी इस तरह के चक्रों को खोजने का एक तरीका प्रदान करता है: यदि कोई चक्र नहीं हैं, तो सभी छोटे रास्ते वी -1 के किनारों की तुलना में नहीं हैं, और अंतिम पुनरावृत्ति में कोई छूट नहीं होगी। उन सभी पसलियों को, जिनकी अंतिम चलने में विश्राम किया गया था, नकारात्मक भार चक्रों में झूठ बोलती हैं, जो प्रारंभिक शीर्ष से उपलब्ध हैं।