सभी-पर्यावरों को कम से कम पथ समस्या को समझना

सभी-जोड़ी लघु पथ (APSP) समस्या वजनी ग्राफ में हर जोड़े के बीच सबसे कम दूरी की तलाश करती है। यह नेटवर्क डिजाइन, यातायात प्रवाह अनुकूलन, सामाजिक नेटवर्क विश्लेषण और रसद के लिए प्रत्यक्ष निहितार्थ के साथ ग्राफ सिद्धांत में एक मूलभूत चुनौती है। एकल-संसाधन लघु पथ समस्याओं के विपरीत, APSP को हल करने के लिए प्रत्येक भंवर से अन्य सभी के लिए दूरी की गणना की आवश्यकता होती है, जो चौगुनी रूप से नोड्स की संख्या के साथ स्केल करता है।

आम दृष्टिकोण इस समस्या को संबोधित करते हैं लेकिन फेस ट्रेड-ऑफ। फ़्लॉइड-वारशॉल, एक गतिशील प्रोग्रामिंग एल्गोरिदम, घने ग्राफ पर काम करता है लेकिन O(V 3 ]]]]]]]]]]]]]] ]] समय और नकारात्मक वजन चक्रों को संभाल नहीं सकता। Dijkstra's एल्गोरिदम, जब प्रत्येक वर्टेक्स से चला जाता है, तो ]O(V (E + V लॉग V)]]] ]]]] एक द्विआधारी हेप के साथ, लेकिन यह नकारात्मक चक्र के तरीकों के लिए नकारात्मक चक्र के लिए उपयुक्त तरीके हैं।

कॉमन एल्गोरिथ्म की तुलना

जॉनसन के एल्गोरिथ्म की सराहना करने के लिए, यह अक्सर इस्तेमाल किए जाने वाले APSP सॉलर्स को विपरीत बनाने में मदद करता है:

  • ]Floyd-Warshall – कार्यान्वयन के लिए सरल, एक 2D दूरी मैट्रिक्स का उपयोग करता है, ट्रिपल छोरों के माध्यम से अद्यतन करता है। नकारात्मक किनारों पर काम करता है लेकिन नकारात्मक चक्र नहीं। क्यूबिक समय के कारण हजारों vertices के साथ ग्राफ के लिए अव्यवहारिक।
  • ]Repeated Dijkstra – प्रत्येक vertex से Dijkstra चलाता है। sparse graph पर तेजी से (]O(V E log V)]] Fibonacci ढेर का उपयोग कर), लेकिन गैर नकारात्मक वजन तक ही सीमित है।
  • ]Bellman-Ford (repeated) - नकारात्मक किनारों को संभालती है लेकिन O(V]]2]E]]]]], जो दोनों विकल्पों की तुलना में धीमी है।
  • जॉनसन के अल्गोरिथम - ग्राफ को फिर से भारित करें ताकि सभी किनारों को गैर-नकारात्मक हो जाए, फिर डायजेक्स्ट्रा को दोहराया जाए। यह O(V E + V 2 log V] ] को नकारात्मक भार के साथ स्पर्स ग्राफ के लिए पसंदीदा विकल्प बनाता है।

कैसे जॉनसन के एल्गोरिथ्म वर्क्स

जॉनसन का एल्गोरिदम केवल गैर-नकारात्मक धार भार के साथ एक में नकारात्मक किनारों वाले एक ग्राफ को बदल देता है, जो कि सबसे कम पथों की संरचना को संरक्षित करता है। यह परिवर्तन एक ] potential function] पर निर्भर करता है जो बेलमैन-फोर्ड के एक एकल रन से प्राप्त होता है। एक बार फिर भारित होने के बाद, Dijkstra के एल्गोरिदम को प्रत्येक नोड से सुरक्षित रूप से इस्तेमाल किया जा सकता है। एल्गोरिथ्म में चार चरण होते हैं।

Step 1: सुपर सोर्स नोड जोड़ना

एक नया वर्टेक्स s को ग्राफ में जोड़ा जाता है, जो वजन 0 के किनारे के साथ प्रत्येक मौजूदा वर्टेक्स से जुड़ा होता है। यह अतिरिक्त नोड सबसे कम पथ दूरी को नहीं बदलता क्योंकि कोई भी पथ जो ]s]]] का उपयोग करता है, लागत के बिना परिवर्धन किया जा सकता है।

चरण 2: कंप्यूटिंग संभावित कार्य बेलमैन-फोर्ड के साथ

सुपर स्रोत से बेलमैन-फोर्ड एल्गोरिथ्म को चलाएं s]. क्योंकि s में सभी vertices के लिए शून्य वजन वाले किनारे हैं, एल्गोरिथ्म सबसे कम दूरी की गणना करता है h(v)]] ]]]] से प्रत्येक vertex के लिए ]v]. यह दूरी एक संभावित कार्य के रूप में कार्य करती है। यदि इस रन के दौरान एक नकारात्मक चक्र का पता लगाया जाता है, तो मूल ग्राफ में एक नकारात्मक चक्र है।

चरण 3: ग्राफ को रीवेट करना

h(v)], प्रत्येक किनारे (u, v)]]]] मूल वजन w(u, v)]]]] के साथ मूल वजन ]]]]] के साथ उपयोग करना:

w'(u, v) = w(u, v) + h(u) - h(v)]

यह परिवर्तन गारंटी देता है कि हर भारित बढ़त वजन गैर नकारात्मक है। सबूत त्रिकोण असमानता पर निर्भर करता है: क्योंकि h(v) ≤ h(u) + w(u, v) (Balman-Ford के उत्पादन से) यह इस बात का अनुसरण करता है कि w'(u, v) ≥ 0]]]]. इसके अलावा, पथ के आदेश संरक्षित है: मूल ग्राफ में किसी भी दो vertices के बीच सबसे छोटा रास्ता reweighted graph में सबसे छोटा रास्ता है।

स्टेप 4: प्रत्येक वर्टेक्स से डिज्क्रा के एल्गोरिथ्म को चलाना

केवल गैर-नकारात्मक किनारों वाले रीवेटेड ग्राफ के साथ, डिजक्रा का एल्गोरिथ्म हर वर्टेक्स से एक बार चला जाता है। प्रत्येक रन अन्य सभी vertices के लिए सबसे कम दूरी की गणना करता है। परिणामस्वरूप दूरी तब सूत्र का उपयोग करके मूल किनारे के वजन में बदल जाती है:

distoriginal(u, v) = dist]reweighted(u, v)](u)+h(v)]]]]]

यह अंतिम चरण यह सुनिश्चित करता है कि रिपोर्ट की गई दूरी मूल ग्राफ के लिए सटीक है।

जटिलता और प्रदर्शन विश्लेषण

जॉनसन का एल्गोरिदम O(V E + V ]2 ]] की समग्र समय जटिलता को प्राप्त करता है, जब एक द्विआधारी हेप प्राथमिकता queue के साथ कार्यान्वित किया जाता है। बेलमैन-फोर्ड कदम O(V E) ]], and the next ]] ] ]] ] ] ] [FLT: [F:]]] [FLT: [F:]]] [FLT]] [F: [F: [F: [F: [F: [F: [F]]]]]]]]] [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F: [F:]]]]]]]]]]]]]]]]]]]]]

एक Fibonacci heap का उपयोग करने से Dijkstra के हिस्से को O(V E + V]2]] log V]]] को कम किया जा सकता है, हालांकि अभ्यास में द्विआधारी ढेर सरल हैं और अक्सर काफी तेज़ हैं। मेमोरी पदचिह्न O(V]]]]]]]]]]]]]] ]] दूरी मैट्रिक्स के लिए, लेकिन यह परिणाम के संग्रहण के द्वारा बेहतर किया जा सकता है।

प्रैक्टिकल अनुप्रयोग

जॉनसन का एल्गोरिदम उन डोमेन में कार्यरत है जहां ग्राफ के किनारे नकारात्मक लागत ले सकते हैं और सभी-जोड़ी छोटी दूरी की आवश्यकता होती है। रियल-वर्ल्ड उदाहरणों में शामिल हैं:

  • ]Network routing: इंटरनेट सेवा प्रदाताओं और दूरसंचार नेटवर्क वितरित रूटिंग प्रोटोकॉल का उपयोग करते हैं जिन्हें किसी भी दो रूटर के बीच अनुकूल रूप से सबसे सस्ता पथ की गणना करनी चाहिए, भले ही लिंक लागत में उतार-चढ़ाव हो या नकारात्मक हो (उदाहरण के लिए, भीड़ या नीति छूट के कारण).
  • ]Urban परिवहन योजना: मैपिंग और रसद कंपनियों (जैसे, गूगल मैप्स, OpenStreetMap रूटिंग इंजन) बेड़े अनुकूलन के लिए कई मूल गंतव्य जोड़ों के बीच सबसे कम पथों को गणना करते हैं। नकारात्मक भार सब्सिडी या समय आधारित छूट को मॉडल कर सकते हैं।
  • ]Supply श्रृंखला लागत न्यूनीकरण: बहु-चरण उत्पादन नेटवर्क में, एक नोड से दूसरे तक की लागत नकारात्मक हो सकती है (जैसे, छूट)। जॉनसन के एल्गोरिदम को पूरी आपूर्ति श्रृंखला में सबसे लाभदायक मार्गों को ढूंढता है।
  • ]Social नेटवर्क विश्लेषण: मापन करीबीता केंद्रीयता या बीच की केंद्रता को सभी-जोड़ी दूरी की आवश्यकता होती है। नकारात्मक पक्ष "दोस्तों के दोस्त" छूट लिंक या प्रतिकूल संबंधों का प्रतिनिधित्व कर सकते हैं।
  • ]Economic इनपुट आउटपुट मॉडल: Leontief मॉडल और प्रवाह विश्लेषण अक्सर नकारात्मक गुणांक शामिल हैं; जॉनसन का एल्गोरिदम एक इंटरकनेक्टेड अर्थव्यवस्था के माध्यम से परिवर्तनों को फैलाने के शुद्ध प्रभाव को पूरा करता है।

गणितीय नींव पर आगे पढ़ने के लिए, देखें Wikipedia's विस्तृत प्रविष्टि और मूल कागज डोनाल्ड B. Johnson (1977) द्वारा। पायथन में एक व्यावहारिक कार्यान्वयन ]]NetworkX के गिटहब repository], जिसमें जॉनसन के एल्गोरिथ्म को एक मानक कार्य के रूप में शामिल किया गया है। रीवेटिंग तकनीक की गहरी समझ के लिए, CP-Algorithms एक स्पष्ट कदम-by-step ट्यूटोरियल प्रदान करता है।

निष्कर्ष

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

जब वास्तविक दुनिया APSP समस्या का सामना करना पड़ा जहां ग्राफ sparse हैं और नकारात्मक किनारों को शामिल कर सकते हैं, तो जॉनसन का एल्गोरिदम पहला विचार होना चाहिए। पुस्तकालयों में इसकी सैद्धांतिक गारंटी और व्यापक कार्यान्वयन (जैसे, NetworkX, ]boost Graph Library]]]) इसे अपनाने के लिए व्यावहारिक बनाती है।