अल्पतम पथ समस्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Computational problem of graph theory}}
{{short description|Computational problem of graph theory}}
[[File:Shortest path with direct weights.svg|thumb|upright=1.2|भारित निर्देशित ग्राफ़ में शीर्ष A एवं  F के मध्य  सबसे छोटा पथ (A, C, E, D, F)।]]
[[File:Shortest path with direct weights.svg|thumb|upright=1.2|ज्ञातित निर्देशित ग्राफ़ में शीर्ष A एवं  F के मध्य  सबसे छोटा पथ (A, C, E, D, F)।]]
{{Tree search algorithm}}
{{Tree search algorithm}}
ग्राफ़ सिद्धांत में, सबसे छोटी पथ समस्या ग्राफ़ (असतत गणित) में दो ऊर्ध्वाधर (ग्राफ़ सिद्धांत) (या नोड्स) के मध्य पथ (ग्राफ़ सिद्धांत) अवलोकन की समस्या है, जैसे [[शिखर ([[ग्राफ सिद्धांत]])]] इसके घटक किनारों के भार का योग अल्प किया गया है।
ग्राफ़ सिद्धांत में, सबसे छोटी पथ समस्या ग्राफ़ (असतत गणित) में दो ऊर्ध्वाधर (ग्राफ़ सिद्धांत) (या नोड्स) के मध्य पथ (ग्राफ़ सिद्धांत) अवलोकन की समस्या है, जैसे [[शिखर ([[ग्राफ सिद्धांत]])]] इसके घटक किनारों के ज्ञात का योग अल्प किया गया है।


मार्ग के मानचित्र पर दो निकटम के मध्य पथ अवलोकन की समस्या को ग्राफ़ में समस्या के विशेष हानि के रूप में तैयार किया जा सकता है, जहाँ कोने निकटम के अनुरूप होते हैं एवं किनारे मार्ग खंडों के अनुरूप होते हैं, प्रत्येक की लंबाई द्वारा भारित खंड है।
मार्ग के मानचित्र पर दो निकटम के मध्य पथ अवलोकन की समस्या को ग्राफ़ में समस्या के विशेष हानि के रूप में तैयार किया जा सकता है, जहाँ कोने निकटम के अनुरूप होते हैं एवं किनारे मार्ग खंडों के अनुरूप होते हैं, प्रत्येक की लंबाई द्वारा ज्ञातित खंड है।


== परिभाषा ==
== परिभाषा ==
Line 13: Line 13:
( <math>v_i</math> चर हैं; यहां नंबरिंग अनुक्रम में स्थिति से संबंधित है एवं ऊर्ध्वाधर के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)
( <math>v_i</math> चर हैं; यहां नंबरिंग अनुक्रम में स्थिति से संबंधित है एवं ऊर्ध्वाधर के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)


<math>e_{i, j}</math> दोनों के लिए किनारे की घटना <math>v_i</math> एवं  <math>v_j</math>हो। दिया गया फंक्शन (गणित) रियल फंक्शन है। रियल-वैल्यूड वेट फंक्शन <math>f: E \rightarrow \mathbb{R}</math>, एवं अप्रत्यक्ष (सरल) ग्राफ <math>G</math>, से सबसे छोटा मार्ग <math>v</math> को <math>v'</math> मार्ग है <math>P = ( v_1, v_2, \ldots, v_n )</math> है, (जहाँ <math>v_1 = v</math> एवं  <math>v_n = v'</math>) वह सब संभव है <math>n</math> योग को अल्प करता है।<math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> जब ग्राफ़ में प्रत्येक किनारे का इकाई भार होता है या <math>f: E \rightarrow \{1\}</math>, यह सबसे अल्प किनारों वाला मार्ग अवलोकन के समान है।
<math>e_{i, j}</math> दोनों के लिए किनारे की घटना <math>v_i</math> एवं  <math>v_j</math>हो। दिया गया फंक्शन (गणित) रियल फंक्शन है। रियल-वैल्यूड वेट फंक्शन <math>f: E \rightarrow \mathbb{R}</math>, एवं अप्रत्यक्ष (सरल) ग्राफ <math>G</math>, से सबसे छोटा मार्ग <math>v</math> को <math>v'</math> मार्ग है <math>P = ( v_1, v_2, \ldots, v_n )</math> है, (जहाँ <math>v_1 = v</math> एवं  <math>v_n = v'</math>) वह सब संभव है <math>n</math> योग को अल्प करता है।<math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> जब ग्राफ़ में प्रत्येक किनारे का इकाई ज्ञात होता है या <math>f: E \rightarrow \{1\}</math>, यह सबसे अल्प किनारों वाला मार्ग अवलोकन के समान है।


समस्या को कभी-कभी एकल-जोड़ी सबसे छोटी पथ समस्या भी कहा जाता है, इसे निम्नलिखित विविधताओं से भिन्न करने के लिए:
समस्या को कभी-कभी एकल-जोड़ी सबसे छोटी पथ समस्या भी कहा जाता है, इसे निम्नलिखित विविधताओं से भिन्न करने के लिए:
Line 24: Line 24:
== एल्गोरिदम ==
== एल्गोरिदम ==
इस समस्या का समाधान करने के लिए सबसे महत्वपूर्ण एल्गोरिदम हैं:
इस समस्या का समाधान करने के लिए सबसे महत्वपूर्ण एल्गोरिदम हैं:
* दिज्क्स्ट्रा का एल्गोरिथ्म गैर-नकारात्मक किनारे के भार के साथ एकल-स्रोत सबसे छोटी पथ समस्या का समाधान करता है।
* दिज्क्स्ट्रा का एल्गोरिथ्म गैर-नकारात्मक किनारे के ज्ञात के साथ एकल-स्रोत सबसे छोटी पथ समस्या का समाधान करता है।
* बेलमैन-फोर्ड एल्गोरिथम एकल-स्रोत समस्या का समाधान करता है यदि किनारे का भार नकारात्मक हो सकता है।
* बेलमैन-फोर्ड एल्गोरिथम एकल-स्रोत समस्या का समाधान करता है यदि किनारे का ज्ञात नकारात्मक हो सकता है।
* अनुसंधान को गति देने के प्रयास करने के लिए ह्यूरिस्टिक्स का उपयोग करके समाधान किया जाता है।
* अनुसंधान को गति देने के प्रयास करने के लिए ह्यूरिस्टिक्स का उपयोग करके समाधान किया जाता है।
* फ्लोयड-वॉर्शल एल्गोरिथम प्रत्येक जोड़ियों के सबसे छोटे मार्ग का समाधान करता है।
* फ्लोयड-वॉर्शल एल्गोरिथम प्रत्येक जोड़ियों के सबसे छोटे मार्ग का समाधान करता है।
* जॉनसन का एल्गोरिदम प्रत्येक जोड़ों को सबसे छोटा मार्ग का समाधान करता है, [[विरल ग्राफ]] पर फ़्लॉइड-वारशाल से तीव्र हो सकता है।
* जॉनसन का एल्गोरिदम प्रत्येक जोड़ों को सबसे छोटा मार्ग का समाधान करता है, [[विरल ग्राफ]] पर फ़्लॉइड-वारशाल से तीव्र हो सकता है।
* वितरबी (Viterbi) एल्गोरिथ्म प्रत्येक नोड पर अतिरिक्त संभाव्य भार के साथ सबसे छोटी स्टोकेस्टिक पथ समस्या का समाधान करता है।
* वितरबी (Viterbi) एल्गोरिथ्म प्रत्येक नोड पर अतिरिक्त संभाव्य ज्ञात के साथ सबसे छोटी स्टोकेस्टिक पथ समस्या का समाधान करता है।


अतिरिक्त एल्गोरिदम एवं संबद्ध मूल्यांकन में {{harvtxt|चर्कास्की|गोल्डबर्ग|रेडज़िक |1996}} प्राप्त किये जाते है।
अतिरिक्त एल्गोरिदम एवं संबद्ध मूल्यांकन में {{harvtxt|चर्कास्की|गोल्डबर्ग|रेडज़िक |1996}} प्राप्त किये जाते है।
Line 50: Line 50:




=== भारित रेखांकन ===
=== ज्ञातित रेखांकन ===
{| class=wikitable
{| class=wikitable
! अल्गोरिथिम !! [[Time complexity|समय जटिलता]] !! लेखक  
! अल्गोरिथिम !! [[Time complexity|समय जटिलता]] !! लेखक  
Line 59: Line 59:


=== निर्देशित विश्वकोश रेखांकन (DAGs) ===
=== निर्देशित विश्वकोश रेखांकन (DAGs) ===
टोपोलोजिकल परिणाम का उपयोग करने वाला एल्गोरिदम इच्छानुसार से भारित डीएजी में समय {{math|Θ(''E'' + ''V'')}} में एकल स्रोत की सबसे छोटी पथ समस्या का समाधान कर सकता है।<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>
टोपोलोजिकल परिणाम का उपयोग करने वाला एल्गोरिदम इच्छानुसार से ज्ञातित डीएजी में समय {{math|Θ(''E'' + ''V'')}} में एकल स्रोत की सबसे छोटी पथ समस्या का समाधान कर सकता है।<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>


=== गैर-ऋणात्मक भार के साथ निर्देशित रेखांकन ===
=== गैर-ऋणात्मक ज्ञात के साथ निर्देशित रेखांकन ===
निम्न सारणी कुछ सुधारों और परिवर्धन के साथ {{harvtxt|श्रिजवर|2004}} से ली गई है। हरे रंग की पृष्ठभूमि सारणी में असम्बद्ध रूप से सर्वोत्तम बाउंड को प्रदर्शित करती है; L प्रत्येक किनारों के मध्य अधिकतम लंबाई (या वजन) है, जो पूर्णांक किनारे भार मानते हैं।
निम्न सारणी कुछ सुधारों और परिवर्धन के साथ {{harvtxt|श्रिजवर|2004}} से ली गई है। हरे रंग की पृष्ठभूमि सारणी में असम्बद्ध रूप से सर्वोत्तम बाउंड को प्रदर्शित करती है; L प्रत्येक किनारों के मध्य अधिकतम लंबाई (या वजन) है, जो पूर्णांक किनारे ज्ञात मानते हैं।
{| class=wikitable
{| class=wikitable
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
Line 91: Line 91:




=== नकारात्मक चक्रों के बिना इच्छानुसार भार के साथ निर्देशित रेखांकन ===
=== नकारात्मक चक्रों के बिना इच्छानुसार ज्ञात के साथ निर्देशित रेखांकन ===
{| class=wikitable
{| class=wikitable
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
Line 118: Line 118:




=== नकारात्मक चक्रों के साथ इच्छानुसार भार के साथ निर्देशित रेखांकन ===
=== नकारात्मक चक्रों के साथ इच्छानुसार ज्ञात के साथ निर्देशित रेखांकन ===
ऋणात्मक चक्र अवलोकन है या प्रत्येक शीर्षों के लिए दूरियों की गणना करता है।
ऋणात्मक चक्र अवलोकन है या प्रत्येक शीर्षों के लिए दूरियों की गणना करता है।
{| class=wikitable
{| class=wikitable
Line 128: Line 128:




=== गैर-ऋणात्मक भार के साथ समतल रेखांकन ===
=== गैर-ऋणात्मक ज्ञात के साथ समतल रेखांकन ===
{| class=wikitable
{| class=wikitable
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
Line 178: Line 178:
[[संगणक संजाल]] या [[दूरसंचार नेटवर्क]] मानसिकता में, इस सबसे छोटी पथ समस्या को कभी-कभी न्यूनतम-विलंब पथ समस्या कहा जाता है एवं सामान्यतः व्यापक पथ समस्या से जुड़ा होता है। उदाप्रत्येकण के लिए, एल्गोरिथ्म सबसे छोटा (न्यूनतम-विलंब) चौड़ा पथ, या सबसे छोटा (न्यूनतम-विलंब) पथ का अन्वेषण कर सकता है।
[[संगणक संजाल]] या [[दूरसंचार नेटवर्क]] मानसिकता में, इस सबसे छोटी पथ समस्या को कभी-कभी न्यूनतम-विलंब पथ समस्या कहा जाता है एवं सामान्यतः व्यापक पथ समस्या से जुड़ा होता है। उदाप्रत्येकण के लिए, एल्गोरिथ्म सबसे छोटा (न्यूनतम-विलंब) चौड़ा पथ, या सबसे छोटा (न्यूनतम-विलंब) पथ का अन्वेषण कर सकता है।


अधिक प्रकाशमय अनुप्रयोग छह डिग्री के अलगाव का खेल है जो ही फिल्म में दिखाई देने वाले फिल्मी सितारों के जैसे रेखांकन में सबसे छोटा मार्ग अवलोकन की कोशिश करता है।
अधिक प्रकाशमय अनुप्रयोग छह डिग्री के अलगाव का खेल है जो ही फिल्म में दिखाई देने वाले फिल्मी सितारों के जैसे रेखांकन में सबसे छोटा मार्ग अवलोकन का प्रयास करता है।


संचालन अनुसंधान में अक्सर अध्ययन किए जाने वाले अन्य अनुप्रयोगों में संयंत्र एवं सुविधा लेआउट,[[रोबोटिक|रोबोटिक्स]], परिवहन एवं बहुत [[बड़े पैमाने पर एकीकरण]] डिजाइन शामिल हैं।<ref>{{cite journal |doi=10.1145/242224.242246 |title=Developing algorithms and software for geometric path planning problems |date=December 1996 |first=Danny Z. |last=Chen |journal=ACM Computing Surveys |volume=28 |issue=4es |s2cid=11761485 |at=Article 18 }}</ref>
संचालन अनुसंधान में अक्सर अध्ययन किए जाने वाले अन्य अनुप्रयोगों में संयंत्र एवं सुविधा लेआउट,[[रोबोटिक|रोबोटिक्स]], परिवहन एवं बहुत [[बड़े पैमाने पर एकीकरण]] डिजाइन उपस्थित हैं।<ref>{{cite journal |doi=10.1145/242224.242246 |title=Developing algorithms and software for geometric path planning problems |date=December 1996 |first=Danny Z. |last=Chen |journal=ACM Computing Surveys |volume=28 |issue=4es |s2cid=11761485 |at=Article 18 }}</ref>




=== मार्ग नेटवर्क ===
=== मार्ग नेटवर्क ===
मार्ग नेटवर्क को सकारात्मक भार वाले ग्राफ के रूप में माना जा सकता है। नोड्स मार्ग जंक्शनों का प्रतिनिधित्व करते हैं एवं  ग्राफ के प्रत्येक किनारे को दो जंक्शनों के मध्य मार्ग खंड से जोड़ा जाता है। किनारे का भार संबंधित मार्ग खंड की लंबाई, खंड को पार करने के लिए आवश्यक समय, या खंड को पार करने की लागत के अनुरूप हो सकता है। निर्देशित किनारों का उपयोग करके तरफ़ा सड़कों का मॉडल बनाना भी संभव है। इस तरह के ग्राफ इस मायने में खास हैं कि लंबी दूरी की यात्रा (जैसे राजमार्ग) के लिए कुछ किनारे दूसरों की तुलना में अधिक महत्वपूर्ण हैं। राजमार्ग आयाम की धारणा का उपयोग करके इस संपत्ति को औपचारिक रूप दिया गया है।<ref>Abraham, Ittai; Fiat, Amos; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/115272/soda10.pdf%20research.microsoft.com/pubs/115272/soda10.pdf "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms"]. ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.</ref> बड़ी संख्या में एल्गोरिदम हैं जो इस संपत्ति का फायदा उठाते हैं एवं यह कारण है की सामान्य ग्राफ़ पर जितना संभव हो उतना तेज़ पथ की गणना करने में सक्षम हैं।
मार्ग नेटवर्क को सकारात्मक ज्ञात वाले ग्राफ के रूप में माना जा सकता है। नोड्स मार्ग जंक्शनों का प्रतिनिधित्व करते हैं एवं  ग्राफ के प्रत्येक किनारे को दो जंक्शनों के मध्य मार्ग खंड से जोड़ा जाता है। किनारे का ज्ञात संबंधित मार्ग खंड की लंबाई, खंड को पार करने के लिए आवश्यक समय, या खंड को पार करने की लागत के अनुरूप हो सकता है। निर्देशित किनारों का उपयोग करके तरफ़ा सड़कों का मॉडल बनाना भी संभव है। इस तरह के ग्राफ इस मायने में खास हैं कि लंबी दूरी की यात्रा (जैसे राजमार्ग) के लिए कुछ किनारे दूसरों की तुलना में अधिक महत्वपूर्ण हैं। राजमार्ग आयाम की धारणा का उपयोग करके इस संपत्ति को औपचारिक रूप दिया गया है।<ref>Abraham, Ittai; Fiat, Amos; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/115272/soda10.pdf%20research.microsoft.com/pubs/115272/soda10.pdf "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms"]. ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.</ref> बड़ी संख्या में एल्गोरिदम हैं जो इस संपत्ति का लाभ उठाते हैं एवं यह कारण है की सामान्य ग्राफ़ पर जितना संभव हो उतना तीव्र पथ की गणना करने में सक्षम हैं।


ये प्रत्येक एल्गोरिदम दो चरणों में काम करते हैं। पूर्वचरण में, स्रोत या लक्ष्य नोड को जाने बिना ग्राफ को प्रीप्रोसेस किया जाता है। दूसरा चरण क्वेरी चरण है। इस चरण में, स्रोत एवं लक्ष्य नोड ज्ञात होते हैं। विचार यह है कि मार्ग नेटवर्क स्थिर है, इसलिए प्रीप्रोसेसिंग चरण किया जा सकता है एवं उसी मार्ग नेटवर्क पर बड़ी संख्या में प्रश्नों के लिए उपयोग किया जा सकता है।
ये प्रत्येक एल्गोरिदम दो चरणों में काम करते हैं। पूर्वचरण में, स्रोत या लक्ष्य नोड को जाने बिना ग्राफ को प्रीप्रोसेस किया जाता है। दूसरा चरण क्वेरी चरण है। इस चरण में, स्रोत एवं लक्ष्य नोड ज्ञात होते हैं। विचार यह है कि मार्ग नेटवर्क स्थिर है, इसलिए प्रीप्रोसेसिंग चरण किया जा सकता है एवं उसी मार्ग नेटवर्क पर बड़ी संख्या में प्रश्नों के लिए उपयोग किया जा सकता है।
Line 213: Line 213:


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


=== नकारात्मक चक्र पहचान ===
=== नकारात्मक चक्र पहचान ===

Revision as of 09:11, 1 March 2023

ज्ञातित निर्देशित ग्राफ़ में शीर्ष A एवं F के मध्य सबसे छोटा पथ (A, C, E, D, F)।

Template:Tree search algorithm ग्राफ़ सिद्धांत में, सबसे छोटी पथ समस्या ग्राफ़ (असतत गणित) में दो ऊर्ध्वाधर (ग्राफ़ सिद्धांत) (या नोड्स) के मध्य पथ (ग्राफ़ सिद्धांत) अवलोकन की समस्या है, जैसे [[शिखर (ग्राफ सिद्धांत)]] इसके घटक किनारों के ज्ञात का योग अल्प किया गया है।

मार्ग के मानचित्र पर दो निकटम के मध्य पथ अवलोकन की समस्या को ग्राफ़ में समस्या के विशेष हानि के रूप में तैयार किया जा सकता है, जहाँ कोने निकटम के अनुरूप होते हैं एवं किनारे मार्ग खंडों के अनुरूप होते हैं, प्रत्येक की लंबाई द्वारा ज्ञातित खंड है।

परिभाषा

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

दो शीर्ष आसन्न होते हैं जब वे दोनों उभयनिष्ठ किनारे पर आपतित होते हैं। अप्रत्यक्ष ग्राफ में पथ शीर्षों का क्रम है। ऐसा है कि है के लिए . ऐसा मार्ग लंबाई का मार्ग कहा जाता है से को है।

( चर हैं; यहां नंबरिंग अनुक्रम में स्थिति से संबंधित है एवं ऊर्ध्वाधर के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)

दोनों के लिए किनारे की घटना एवं हो। दिया गया फंक्शन (गणित) रियल फंक्शन है। रियल-वैल्यूड वेट फंक्शन , एवं अप्रत्यक्ष (सरल) ग्राफ , से सबसे छोटा मार्ग को मार्ग है है, (जहाँ एवं ) वह सब संभव है योग को अल्प करता है। जब ग्राफ़ में प्रत्येक किनारे का इकाई ज्ञात होता है या , यह सबसे अल्प किनारों वाला मार्ग अवलोकन के समान है।

समस्या को कभी-कभी एकल-जोड़ी सबसे छोटी पथ समस्या भी कहा जाता है, इसे निम्नलिखित विविधताओं से भिन्न करने के लिए:

  • एकल-स्रोत लघुतम पथ समस्या, जिसमें हमें किसी स्रोत शीर्ष v से ग्राफ़ में अन्य प्रत्येक शीर्षों तक सबसे छोटा पथ अवलोकन करना होता है।
  • एकल-गंतव्य लघुतम पथ समस्या, जिसमें हमें डायरेक्टेड ग्राफ में प्रत्येक ऊर्ध्वाधर v तक सबसे छोटा पथ अवलोकन करना होता है। डायरेक्टेड ग्राफ में आर्क्स को परिवर्तित करके इसे एकल-गंतव्य लघुतम पथ समस्या में घटाया जा सकता है।
  • जोड़े सबसे छोटी पथ समस्या, जिसमें हमें ग्राफ में ऊर्ध्वाधर v, v' के प्रत्येक जोड़े के मध्य सबसे छोटा मार्ग अवलोकन करना होता है।

इन सामान्यीकरणों में प्रत्येक प्रासंगिक जोड़ों के शीर्ष पर एकल-जोड़ी सबसे छोटा पथ एल्गोरिदम चलाने के सरलीकृत दृष्टिकोण की तुलना में अधिक कुशल एल्गोरिदम हैं।

एल्गोरिदम

इस समस्या का समाधान करने के लिए सबसे महत्वपूर्ण एल्गोरिदम हैं:

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

अतिरिक्त एल्गोरिदम एवं संबद्ध मूल्यांकन में चर्कास्की, गोल्डबर्ग & रेडज़िक (1996) प्राप्त किये जाते है।

एकल-स्रोत सबसे छोटा पथ

अप्रत्यक्ष रेखांकन

वेइट्स समय जटिलता लेखक
+ O(V2) दिज्क्स्ट्रा 1959
+ O((E + V) log V) जॉनसन 1977 (द्विआधारी ढेर)
+ O(E + V log V) फेडमैन & टार्जन 1984 (फाइबोनैचि हीप)
O(E) थोरुप 1999 (निरंतर-समय गुणन की आवश्यकता है)


ज्ञातित रेखांकन

अल्गोरिथिम समय जटिलता लेखक
Breadth-first search O(E + V)


निर्देशित विश्वकोश रेखांकन (DAGs)

टोपोलोजिकल परिणाम का उपयोग करने वाला एल्गोरिदम इच्छानुसार से ज्ञातित डीएजी में समय Θ(E + V) में एकल स्रोत की सबसे छोटी पथ समस्या का समाधान कर सकता है।[1]

गैर-ऋणात्मक ज्ञात के साथ निर्देशित रेखांकन

निम्न सारणी कुछ सुधारों और परिवर्धन के साथ श्रिजवर (2004) से ली गई है। हरे रंग की पृष्ठभूमि सारणी में असम्बद्ध रूप से सर्वोत्तम बाउंड को प्रदर्शित करती है; L प्रत्येक किनारों के मध्य अधिकतम लंबाई (या वजन) है, जो पूर्णांक किनारे ज्ञात मानते हैं।

वेइट्स अल्गोरिथिम समय जटिलता लेखक
फोर्ड 1956
बेल्लम फोर्ड अल्गोरिथिम सिम्बल 1955, बेल्लम 1958, मूर 1959
दंतजिग 1960
डिजिस्ट्रा अल्गोरिथिमwith list लेजोरक et al. 1957, डिजिस्ट्रा 1959, मिन्टी (देखो पोलक & विएबैंसों 1960), वव्हिटिंग & हीलिएर 1960
डिजिस्ट्रा अल्गोरिथिम के साथ बाइनरी हीप जॉनसन 1977
डिजिस्ट्रा अल्गोरिथिम के साथ फिबोनैकी हीप फेडमैन & तजरन 1984, फेडमैन & तजरन 1987
डायल अल्गोरिथिम (डिजिस्ट्रा अल्गोरिथिम using a bucket queue with L buckets) डायल 1969
जॉनसन 1981, कार्ल्सोन & पोब्लेट 1983
गबोस अल्गोरिथिम गाबो 1983, गाबो 1985
आहूजा et al. 1990
थोरुप थोरुप 2004


नकारात्मक चक्रों के बिना इच्छानुसार ज्ञात के साथ निर्देशित रेखांकन

वेइट्स अल्गोरिथिम समय जटिलता लेखक
O(V 2EL) फोर्ड 1956
बेल्लम फोर्ड अल्गोरिथिम O(VE) सिम्बल 1955, बेल्लम 1958, मूर 1959
जॉनसन-डिजिस्ट्रा बाइनरी हीप के साथ O(V (E + log V)) जॉनसन 1977
जॉनसन-डिजिस्ट्रा फिबोनैकी  हीप के साथ O(V (E + log V)) फ्रेडमन & तजरन 1984, फ्रेडमन & तजरन 1987, जॉनसन 1977के बाद अनुकूलित
जॉनसन-डायल अल्गोरिथिम पर लागू तकनीक[2] O(V (E + L)) डायल 1969, जॉनसन 1977के बाद अनुकूलित


नकारात्मक चक्रों के साथ इच्छानुसार ज्ञात के साथ निर्देशित रेखांकन

ऋणात्मक चक्र अवलोकन है या प्रत्येक शीर्षों के लिए दूरियों की गणना करता है।

वेइट्स अल्गोरिथिम समय जटिलता लेखक
एंड्रयू वी गोल्डबर्ग


गैर-ऋणात्मक ज्ञात के साथ समतल रेखांकन

वेइट्स अल्गोरिथिम समय जटिलता लेखक
हैंजिनगीर et al. 1997


प्रत्येक जोड़े सबसे छोटा मार्ग

जोड़े सबसे छोटा पथ समस्या ग्राफ में ऊर्ध्वाधर v, v' के प्रत्येक जोड़े के मध्य सबसे छोटा मार्ग का अवलोकन करती है। Shimbel (1953) द्वारा अनिर्धारित डायरेक्टेड ग्राफ के लिए जोड़े सबसे छोटा पथ समस्या किसके द्वारा प्रस्तावित की गई थी? जिन्होंने देखा कि इसे मैट्रिक्स गुणन की रैखिक संख्या द्वारा समाधान किया जा सकता है जिसमें O(V4) कुल समय लगता है। .

अप्रत्यक्ष ग्राफ

वेइट्स समय जटिलता अल्गोरिथिम
+ O(V3) फ्ल्यूड–वर्षल अल्गोरिथिम
सैंडल अल्गोरिथिम
विल्लियम्स 2014
+ O(EV log α(E,V)) पट्टी & रामचंद्रन 2002
O(EV) थोरुप 1999 प्रत्येक शीर्ष पर लागू होता है(निरंतर-समय गुणन की आवश्यकता है).


निर्देशित ग्राफ

वेइट्स समय जटिलता अल्गोरिथिम
(no negative cycles) O(V3) फ्ल्यूड–वर्षल अल्गोरिथिम
विल्लियम्स 2014
(no negative cycles) O(EV + V2 log V) जॉनसन–दंतजिग
(no negative cycles) O(EV + V2 log log V) पट्टी 2004
O(EV + V2 log log V) हाग्रुप 2000


अनुप्रयोग

मैपक्वेस्ट या गूगल मानचित्र जैसी वेब मैपिंग वेबसाइटों पर ड्राइविंग दिशाओं जैसे भौतिक स्थानों के मध्य स्वचालित रूप से दिशाओं को अवलोकन के लिए सबसे छोटा पथ एल्गोरिदम प्रारम्भ किया जाता है। इस एप्लिकेशन के लिए तेजी से विशेष एल्गोरिदम उपलब्ध हैं।[3]यदि कोई ग्राफ के रूप में अन्य -नियतात्मक अमूर्त मशीन का प्रतिनिधित्व करता है, जहां कोने राज्यों एवं किनारों का वर्णन करते हैं, तो संभव संक्रमण का वर्णन करते हैं, निश्चित लक्ष्य स्थिति तक पहुंचने के लिए विकल्पों का इष्टतम अनुक्रम अवलोकनके लिए, या आवश्यक समय पर अल्प सीमा स्थापित करने के लिए सबसे छोटा पथ एल्गोरिदम का उपयोग किया जा सकता है। किसी दिए गए राज्य तक पहुँचें उदाप्रत्येकण के लिए, यदि कोने रूबिक क्यूब जैसी पहेली की अवस्थाओं का प्रतिनिधित्व करते हैं एवं प्रत्येक निर्देशित किनारा चाल या मोड़ से मेल खाता है, तो सबसे छोटा पथ एल्गोरिदम का उपयोग समाधान अवलोकन के लिए किया जा सकता है जो चालों की न्यूनतम संभव संख्या का उपयोग करता है।

संगणक संजाल या दूरसंचार नेटवर्क मानसिकता में, इस सबसे छोटी पथ समस्या को कभी-कभी न्यूनतम-विलंब पथ समस्या कहा जाता है एवं सामान्यतः व्यापक पथ समस्या से जुड़ा होता है। उदाप्रत्येकण के लिए, एल्गोरिथ्म सबसे छोटा (न्यूनतम-विलंब) चौड़ा पथ, या सबसे छोटा (न्यूनतम-विलंब) पथ का अन्वेषण कर सकता है।

अधिक प्रकाशमय अनुप्रयोग छह डिग्री के अलगाव का खेल है जो ही फिल्म में दिखाई देने वाले फिल्मी सितारों के जैसे रेखांकन में सबसे छोटा मार्ग अवलोकन का प्रयास करता है।

संचालन अनुसंधान में अक्सर अध्ययन किए जाने वाले अन्य अनुप्रयोगों में संयंत्र एवं सुविधा लेआउट,रोबोटिक्स, परिवहन एवं बहुत बड़े पैमाने पर एकीकरण डिजाइन उपस्थित हैं।[4]


मार्ग नेटवर्क

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

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

सबसे तेज़ ज्ञात क्वेरी समय वाले एल्गोरिदम को हब लेबलिंग कहा जाता है एवं यह माइक्रोसेकंड के अंश में यूरोप या यूएस के मार्ग नेटवर्क पर सबसे छोटे पथ की गणना करने में सक्षम है।[6] अन्य तकनीकों का उपयोग किया गया है:

संबंधित समस्याएं

कम्प्यूटेशनल ज्यामिति में सबसे छोटी पथ समस्याओं के लिए, यूक्लिडियन सबसे छोटा मार्ग देखें।

सबसे छोटा एकाधिक डिस्कनेक्ट पथ [7] पुनरावृत्ति सिद्धांत के ढांचे के भीतर आदिम पथ नेटवर्क का प्रतिनिधित्व है। व्यापक पथ समस्या पथ की तलाश करती है चुकीं किसी भी किनारे का न्यूनतम लेबल जितना संभव हो उतना बड़ा हो।

अन्य संबंधित समस्याओं को निम्नलिखित श्रेणियों में वर्गीकृत किया जा सकता है।

बाधाओं के साथ पथ

सबसे छोटी पथ समस्या के विपरीत, जिसे नकारात्मक चक्रों के बिना ग्राफ़ में बहुपद समय में समाधान किया जा सकता है, सबसे छोटी पथ समस्याएँ जिनमें वांछित समाधान पथ पर अतिरिक्त बाधाएँ शामिल होती हैं, उन्हें कंस्ट्रेन्टेड शोर्टेस्ट पाथ फर्स्ट कहा जाता है, एवं समाधान करना कठिन होता है। उदाप्रत्येकण विवश लघुतम पथ समस्या है,[8] जो पथ की कुल लागत को अल्प करने का प्रयास करता है जबकि साथ ही किसी दिए गए थ्रेसहोल्ड के नीचे एवं मीट्रिक बनाए रखता है। यह समस्या को एनपी-पूर्ण बनाता है (ऐसी समस्याओं को डेटा के बड़े सेट के लिए कुशलता से समाधान करने योग्य नहीं माना जाता है, पी = एनपी समस्या देखें)। अन्य एनपी-पूर्ण उदाप्रत्येकण के लिए पथ में शामिल किए जाने वाले ऊर्ध्वाधर के विशिष्ट सेट की आवश्यकता होती है,[9] जो समस्या को ट्रैवलिंग सेल्समैन की समस्या (टीएसपी) के समान बनाता है। टीएसपी सबसे छोटा मार्ग अवलोकनकी समस्या है जो प्रत्येक शीर्ष से ठीक बार गुजरता है, एवं शुरुआत में वापस आ जाता है। ग्राफ़ में सबसे लंबे पथ की समस्या भी एनपी-पूर्ण है।

आंशिक अवलोकनशीलता

कनाडाई यात्री समस्या एवं स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम सामान्यीकरण हैं जहां या तो ग्राफ मूवर को पूरी तरह से ज्ञात नहीं है, समय के साथ बदलता है, या जहां क्रियाएं (ट्रैवर्सल) संभाव्य हैं। [10] [11]


रणनीतिक सबसे छोटा रास्ता

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

नकारात्मक चक्र पहचान

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

  • बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र का पता लगाने के लिए किया जा सकता है .
  • चर्कास्की एवं गोल्डबर्ग[12] नकारात्मक चक्र का पता लगाने के लिए कई अन्य एल्गोरिदम का सर्वेक्षण करें।

सेमीरिंग पर सामान्य बीजगणितीय रूपरेखा: बीजगणितीय पथ समस्या

कई समस्याओं को पथ के साथ जोड़ने एवं न्यूनतम लेने की कुछ उपयुक्त रूप से प्रतिस्थापित धारणाओं के लिए सबसे छोटे पथ के रूप में तैयार किया जा सकता है। इनके लिए सामान्य दृष्टिकोण दो परिचालनों को मोटी हो जाओ के रूप में माना जाता है। सेमिरिंग गुणन पथ के साथ किया जाता है, एवं जोड़ पथों के मध्य होता है। इस सामान्य ढाँचे को बीजगणितीय पथ समस्या के रूप में जाना जाता है।[13][14][15]इस तरह के बीजगणितीय संरचनाओं पर रैखिक प्रणालियों को समाधान करने के रूप में अधिकांश क्लासिक शॉर्टेस्ट-पाथ एल्गोरिदम (एवं नए) तैयार किए जा सकते हैं। हाल ही में, मूल्यांकन बीजगणित के बैनर तले इन (एवं बहुत अल्प स्पष्ट रूप से संबंधित समस्याओं) को समाधान करने के लिए एवं अधिक सामान्य रूपरेखा विकसित की गई है।.[16]


स्टोकेस्टिक टाइम-डिपेंडेंट नेटवर्क्स में सबसे छोटा रास्ता

वास्तविक जीवन की स्थितियों में, परिवहन नेटवर्क सामान्यतः स्टोकेस्टिक एवं समय पर निर्भर होता है। वास्तव में, यात्री प्रतिदिन लिंक पर यात्रा कर रहा है, न केवल यात्रा की मांग (मूल-गंतव्य मैट्रिक्स) में उतार-चढ़ाव के कारण, किंतु कार्य क्षेत्र, खराब मौसम की स्थिति, दुर्घटनाओं एवं वाहन के टूटने जैसी घटनाओं के कारण भी उस लिंक पर यात्रा के अलग-भिन्न समय का अनुभव कर सकता है। नतीजतन, स्टोकास्टिक टाइम-डिपेंडेंट (एसटीडी) नेटवर्क निर्धारिती की तुलना में वास्तविक मार्ग नेटवर्क का अधिक यथार्थवादी प्रतिनिधित्व है।[17][18]पिछले दशक के दौरान काफी प्रगति के बावजूद, यह विवादास्पद प्रश्न बना हुआ है कि स्टोकास्टिक मार्ग नेटवर्क में इष्टतम पथ को कैसे परिभाषित एवं पहचाना जाना चाहिए। दूसरे शब्दों में, अनिश्चितता के तहत इष्टतम पथ की कोई अनूठी परिभाषा नहीं है। इस प्रश्न का संभावित एवं सामान्य उत्तर न्यूनतम अपेक्षित यात्रा समय के साथ मार्ग खोजना है। इस दृष्टिकोण का उपयोग करने का मुख्य लाभ यह है कि नियतात्मक नेटवर्क के लिए प्रस्तावित किए गए कुशल लघुतम पथ एल्गोरिदम को स्टोकेस्टिक नेटवर्क में न्यूनतम अपेक्षित यात्रा समय के साथ पथ की पहचान करने के लिए आसानी से नियोजित किया जा सकता है। चूँकि, इस दृष्टिकोण द्वारा पहचाना गया परिणामी इष्टतम पथ विश्वसनीय नहीं हो सकता है, क्योंकि यह दृष्टिकोण यात्रा समय परिवर्तनशीलता को संबोधित करने में विफल रहता है। इस समस्या से निपटने के लिए कुछ शोधकर्ता इसके अपेक्षित मूल्य के अतिरिक्त यात्रा के समय के वितरण का उपयोग करते हैं, इसलिए वे गतिशील प्रोग्रामिंग एवं दिज्क्स्ट्रा के एल्गोरिथ्म जैसे विभिन्न अनुकूलन विधियों का उपयोग करके कुल यात्रा समय का संभाव्यता वितरण पाते हैं।[19] संभाव्य चाप लंबाई वाले नेटवर्क में सबसे छोटा मार्ग अवलोकनके लिए ये विधियां स्टोचैस्टिक अनुकूलन, विशेष रूप से स्टोकास्टिक गतिशील प्रोग्रामिंग का उपयोग करती हैं।[20] परिवहन अनुसंधान साहित्य में यात्रा समय की विश्वसनीयता की अवधारणा को यात्रा के समय की परिवर्तनशीलता के साथ दूसरे के स्थान पर उपयोग किया जाता है, जिससे, सामान्य तौर पर, यह कहा जा सके कि यात्रा समय में परिवर्तनशीलता जितनी अधिक होगी, विश्वसनीयता उतनी ही अल्प एवं इसके विपरीत होगी।

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

यह भी देखें

संदर्भ

टिप्पणियाँ

  1. Cormen et al. 2001, p. 655
  2. Dial, Robert B. (1969). "Algorithm 360: Shortest-Path Forest with Topological Ordering [H]". Communications of the ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
  3. Sanders, Peter (March 23, 2009). "Fast route planning". Google Tech Talk. Archived from the original on 2021-12-11.
  4. Chen, Danny Z. (December 1996). "Developing algorithms and software for geometric path planning problems". ACM Computing Surveys. 28 (4es). Article 18. doi:10.1145/242224.242246. S2CID 11761485.
  5. Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms". ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.
  6. Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks". Symposium on Experimental Algorithms, pages 230–241, 2011.
  7. Kroger, Martin (2005). "Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems". Computer Physics Communications. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016/j.cpc.2005.01.020.
  8. Lozano, Leonardo; Medaglia, Andrés L (2013). "On an exact method for the constrained shortest path problem". Computers & Operations Research. 40 (1): 378--384. doi:10.1016/j.cor.2012.07.008.
  9. Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search". 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS): 3519--3525. arXiv:2108.01036. doi:10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.
  10. Bar-Noy, Amotz; Schieber, Baruch (1991). "The canadian traveller problem". Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms: 261–270. CiteSeerX 10.1.1.1088.3015.
  11. Nikolova, Evdokia; Karger, David R. "Route planning under uncertainty: the Canadian traveller problem" (PDF). Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI): 969--974. Archived (PDF) from the original on 2022-10-09.
  12. Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "Negative-cycle detection algorithms". Mathematical Programming (in English). 85 (2): 277–311. doi:10.1007/s101070050058. ISSN 1436-4646. S2CID 79739.
  13. Pair, Claude (1967). "Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)". In Rosentiehl, Pierre (ed.). Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium). Rome (Italy), July 1966: Dunod (Paris) et Gordon and Breach (New York). p. 271.{{cite conference}}: CS1 maint: location (link)
  14. Derniame, Jean Claude; Pair, Claude (1971). Problèmes de cheminement dans les graphes (Path Problems in Graphs). Dunod (Paris).
  15. Baras, John; Theodorakopoulos, George (4 April 2010). Path Problems in Networks. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.
  16. Pouly, Marc; Kohlas, Jürg (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. Chapter 6. Valuation Algebras for Path Problems. ISBN 978-1-118-01086-0.
  17. Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
  18. Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm". Expert Systems with Applications. 42 (12): 5056–5064. doi:10.1016/j.eswa.2015.02.046.
  19. Olya, Mohammad Hessam (2014). "Finding shortest path in a combined exponential – gamma probability distribution arc length". International Journal of Operational Research. 21 (1): 25–37. doi:10.1504/IJOR.2014.064020.
  20. Olya, Mohammad Hessam (2014). "Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length". International Journal of Operational Research. 21 (2): 143–154. doi:10.1504/IJOR.2014.064541.


ग्रन्थसूची


अग्रिम पठन

  • Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Fully dynamic output bounded single source shortest path problem". Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms. Atlanta, GA. pp. 212–221. CiteSeerX 10.1.1.32.9856.
  • Dreyfus, S. E. (October 1967). An Appraisal of Some Shortest Path Algorithms (PDF) (Report). Project Rand. United States Air Force. RM-5433-PR. Archived (PDF) from the original on November 17, 2015. DTIC AD-661265.