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

From Vigyanwiki
No edit summary
No edit summary
 
(36 intermediate revisions by 4 users not shown)
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}}
ग्राफ़ सिद्धांत में, '''अल्पतम पथ समस्या''' ग्राफ़ (असतत गणित) में दो ऊर्ध्वाधर (ग्राफ़ सिद्धांत) (या नोड्स) के मध्य पथ (ग्राफ़ सिद्धांत) अवलोकन की समस्या है, जैसे: शिखर ([[ग्राफ सिद्धांत]]) इसके घटक किनारों के भार का योग अल्प किया गया है।
ग्राफ़ सिद्धांत में, सबसे छोटी पथ समस्या ग्राफ़ (असतत गणित) में दो वर्टेक्स (ग्राफ़ सिद्धांत) (या नोड्स) के मध्य पथ (ग्राफ़ सिद्धांत) खोजने की समस्या है, जैसे [[शिखर ([[ग्राफ सिद्धांत]])]] की शब्दावली का योग भारित इसके घटक किनारों का ग्राफ कम किया गया है।


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


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


दो शीर्ष आसन्न होते हैं जब वे दोनों उभयनिष्ठ किनारे पर आपतित होते हैं। पथ (ग्राफ सिद्धांत) अप्रत्यक्ष ग्राफ में वर्टिकल का क्रम है <math>P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V</math> ऐसा है कि <math>v_i</math> लगी हुई है <math>v_{i+1}</math> के लिए <math>1 \leq i < n</math>.
दो शीर्ष आसन्न होते हैं जब वे दोनों उभयनिष्ठ किनारे पर आपतित होते हैं। अप्रत्यक्ष ग्राफ में पथ शीर्षों का क्रम है।<math>P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V</math> ऐसा है कि <math>v_i</math> है <math>v_{i+1}</math> के लिए <math>1 \leq i < n</math>. ऐसा मार्ग <math>P</math> लंबाई का मार्ग कहा जाता है <math>n-1</math> से <math>v_1</math> को <math>v_n</math>है।
ऐसा मार्ग <math>P</math> लंबाई का मार्ग कहा जाता है <math>n-1</math>
से <math>v_1</math> को <math>v_n</math>.
( <math>v_i</math> h> चर हैं; यहां उनकी नंबरिंग अनुक्रम में उनकी स्थिति से संबंधित है एवं  वर्टिकल के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)


होने देना <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>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>, यह सबसे अल्प किनारों वाला मार्ग अवलोकन के समान है।
* सिंगल-सोर्स शॉर्टेस्ट पाथ प्रॉब्लम, जिसमें हमें सोर्स वर्टेक्स ''v'' से ग्राफ में अन्य सभी वर्टिकल तक सबसे छोटा रास्ता खोजना होता है।
* सिंगल-डेस्टिनेशन शॉर्टेस्ट पाथ प्रॉब्लम, जिसमें हमें डायरेक्टेड ग्राफ में सभी वर्टिकल से सिंगल डेस्टिनेशन वर्टेक्स ''v'' तक सबसे छोटा रास्ता खोजना होता है। निर्देशित ग्राफ़ में चापों को उलट कर इसे एकल-स्रोत सबसे छोटी पथ समस्या में कम किया जा सकता है।
* ऑल-पेयर शॉर्टेस्ट पाथ प्रॉब्लम, जिसमें हमें ग्राफ में ''v'', ''v'' वर्टिकल के हर जोड़े के मध्य सबसे छोटा रास्ता खोजना है।


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


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


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


== एकल-स्रोत सबसे छोटा पथ ==
== एकल-स्रोत सबसे छोटा पथ ==
Line 39: Line 36:
=== अप्रत्यक्ष रेखांकन ===
=== अप्रत्यक्ष रेखांकन ===
{| class=wikitable
{| class=wikitable
! Weights !! [[Time complexity]] !! Author
!वेइट्स
! [[Time complexity|समय जटिलता]] !! लेखक
|-
|-
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''V<sup>2</sup>'') || {{harvnb|Dijkstra|1959}}
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''V<sup>2</sup>'') || {{harvnb|दिज्क्स्ट्रा|1959}}
|-
|-
| <math>\mathbb{R}</math><sub>+</sub>  || ''O''((''E''&nbsp;+&nbsp;''V'')&nbsp;log&nbsp;''V'') || {{harvnb|Johnson|1977}} ([[binary heap]])
| <math>\mathbb{R}</math><sub>+</sub>  || ''O''((''E''&nbsp;+&nbsp;''V'')&nbsp;log&nbsp;''V'') || {{harvnb|जॉनसन 1977 (द्विआधारी ढेर)|}}
|-
|-
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''E''&nbsp;+&nbsp;''V''&nbsp;log&nbsp;''V'') || {{harvnb|Fredman|Tarjan|1984}} ([[Fibonacci heap]])
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''E''&nbsp;+&nbsp;''V''&nbsp;log&nbsp;''V'') || {{harvnb|फेडमैन|टार्जन 1984 (फाइबोनैचि हीप)|}}  
|-
|-
| <math>\mathbb{N}</math> || ''O''(''E'') || {{harvnb|Thorup|1999}} (requires constant-time multiplication)
| <math>\mathbb{N}</math> || ''O''(''E'') || थोरुप 1999 (निरंतर-समय गुणन की आवश्यकता है)
|}
|}


Line 53: Line 51:
=== भारित रेखांकन ===
=== भारित रेखांकन ===
{| class=wikitable
{| class=wikitable
! Algorithm !! Time complexity !! Author
! अल्गोरिथिम !! [[Time complexity|समय जटिलता]] !! लेखक
|-
|-
| [[Breadth-first search]] || ''O''(''E''&nbsp;+&nbsp;''V'') ||
| [[Breadth-first search]] || ''O''(''E''&nbsp;+&nbsp;''V'') ||
Line 60: Line 58:


=== निर्देशित विश्वकोश रेखांकन (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|Schrijver|2004}}, कुछ सुधार एवं  परिवर्धन के साथ।
निम्न सारणी कुछ सुधारों और परिवर्धन के साथ {{harvtxt|श्रिजवर|2004}} से ली गई है। हरे रंग की पृष्ठभूमि सारणी में असम्बद्ध रूप से सर्वोत्तम बाउंड को प्रदर्शित करती है; L प्रत्येक किनारों के मध्य अधिकतम लंबाई (या वजन) है, जो पूर्णांक किनारे भार मानते हैं।
हरे रंग की पृष्ठभूमि तालिका में असम्बद्ध रूप से सर्वोत्तम बाउंड को इंगित करती है; एल सभी किनारों के मध्य अधिकतम लंबाई (या वजन) है, जो पूर्णांक किनारे भार मानते हैं।
{| class=wikitable
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
|-
|-
| <math>\mathbb{R}</math> || || <math>O(V^2EL)</math> || {{harvnb|Ford|1956}}
| <math>\mathbb{R}</math> || || <math>O(V^2EL)</math> || {{harvnb|फोर्ड |1956}}
|-
|-
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm]] || <math>O(VE)</math> || {{harvnb|Shimbel|1955}}, {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm|बेल्लम फोर्ड अल्गोरिथिम]] || <math>O(VE)</math> || {{harvnb|सिम्बल|1955}}, {{harvnb|बेल्लम |1958}}, {{harvnb|मूर|1959}}
|-
|-
| <math>\mathbb{R}</math> || || <math>O(V^2 \log{V})</math> || {{harvnb|Dantzig|1960}}
| <math>\mathbb{R}</math> || || <math>O(V^2 \log{V})</math> || {{harvnb|दंतजिग |1960}}
|-
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with list || <math>O(V^2)</math> || {{harvnb|Leyzorek|Gray|Johnson|Ladew|1957}}, {{harvnb|Dijkstra|1959}}, Minty (see {{harvnb|Pollack|Wiebenson|1960}}), {{harvnb|Whiting|Hillier|1960}}
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm|डिजिस्ट्रा अल्गोरिथिम]]<nowiki/> सूची के साथ || <math>O(V^2)</math> || {{harvnb| लेजोरक |Gray|Johnson|Ladew|1957}}, {{harvnb|डिजिस्ट्रा |1959}}, मिन्टी (देखो {{harvnb| पोलक|विएबैंसों|1960}}), {{harvnb|वव्हिटिंग| हीलिएर|1960}}
|-
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[binary heap]] || <math> O((E+V)\log{V})</math> || {{harvnb|Johnson|1977}}
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm|डिजिस्ट्रा अल्गोरिथिम]] के साथ  [[binary heap|बाइनरी हीप]]|| <math> O((E+V)\log{V})</math> || {{harvnb|जॉनसन  |1977}}
|- style="background: #d0ffd0"
|- style="background: #d0ffd0"
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[Fibonacci heap]]||<math>O(E+V\log{V})</math> || {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm|डिजिस्ट्रा अल्गोरिथिम]] के साथ [[Fibonacci heap|फिबोनैकी हीप]]||<math>O(E+V\log{V})</math> || {{harvnb|फेडमैन|तजरन |1984}}, {{harvnb|फेडमैन|तजरन |1987}}
|-
|-
| <math>\mathbb{N}</math> || Dial's algorithm<ref name="dial69">{{cite journal
| <math>\mathbb{N}</math> || डायल अल्गोरिथिम ([[Dijkstra's algorithm|डिजिस्ट्रा अल्गोरिथिम]] using a [[bucket queue]] with ''L'' buckets) || <math>O(E+LV)</math> || {{harvnb|डायल|1969}}
  | last = Dial | first = Robert B.
  | title = Algorithm 360: Shortest-Path Forest with Topological Ordering [H]
  | journal = Communications of the ACM
  | volume = 12
  | issue = 11
  | pages = 632–633
  | year = 1969
  | doi = 10.1145/363269.363610
  | s2cid = 6754003
| doi-access = free
  }}</ref> ([[Dijkstra's algorithm]] using a [[bucket queue]] with ''L'' buckets) || <math>O(E+LV)</math> || {{harvnb|Dial|1969}}
|-
|-
|- style="background: #d0ffd0"
|- style="background: #d0ffd0"
| || || <math>O(E\log{\log{L}})</math> || {{harvnb|Johnson|1981}}, {{harvnb|Karlsson|Poblete|1983}}
| || || <math>O(E\log{\log{L}})</math> || {{harvnb|जॉनसन  |1981}}, {{harvnb|कार्ल्सोन|पोब्लेट|1983}}
|-
|-
| || [[Gabow's algorithm (single-source shortest paths)|Gabow's algorithm]] || <math>O(E\log_{E/V}L) </math>|| {{harvnb|Gabow|1983}}, {{harvnb|Gabow|1985}}
| || [[Gabow's algorithm (single-source shortest paths)|गबोस अल्गोरिथिम]]|| <math>O(E\log_{E/V}L) </math>|| {{harvnb|गाबो |1983}}, {{harvnb|गाबो |1985}}
|- style="background: #d0ffd0"
|- style="background: #d0ffd0"
| || || <math> O( E + V \sqrt{\log{L}})</math> || {{harvnb|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}
| || || <math> O( E + V \sqrt{\log{L}})</math> || {{harvnb|आहूजा|Mehlhorn|Orlin|Tarjan|1990}}
|-
|-
| || Thorup || <math>O(E+V \log{\log{V}})</math>|| {{harvnb|Thorup|2004}}
| || थोरुप || <math>O(E+V \log{\log{V}})</math>|| {{harvnb|थोरुप  |2004}}
|}
|}
{{expand list|date=February 2011}}




=== नकारात्मक चक्रों के बिना मनमाने वजन के साथ निर्देशित रेखांकन ===
=== नकारात्मक चक्रों के बिना इच्छानुसार भार के साथ निर्देशित रेखांकन ===
{| class=wikitable
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
|-
|-
| <math>\mathbb{R}</math> || || ''O''(''V''<sup> 2</sup>''EL'') || {{harvnb|Ford|1956}}
| <math>\mathbb{R}</math> || || ''O''(''V''<sup> 2</sup>''EL'') || {{harvnb|फोर्ड|1956}}
|-
|-
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm]] || ''O''(''VE'') || {{harvnb|Shimbel|1955}}, {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
| <math>\mathbb{R}</math> ||   [[Bellman–Ford algorithm|बेल्लम फोर्ड अल्गोरिथिम]] || ''O''(''VE'') || {{harvnb|सिम्बल|1955}}, {{harvnb|बेल्लम |1958}}, {{harvnb|मूर |1959}}
|-
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[binary heap]] || ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;log&nbsp;''V'')) || {{harvnb|Johnson|1977}}
| <math>\mathbb{R}</math> || [[Johnson's algorithm|जॉनसन-डिजिस्ट्रा]] [[binary heap|बाइनरी हीप के साथ]]|| ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;log&nbsp;''V'')) || {{harvnb|जॉनसन|1977}}
|-
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[Fibonacci heap]] || ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;log&nbsp;''V'')) || {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}, adapted after {{harvnb|Johnson|1977}}
| <math>\mathbb{R}</math> || [[Johnson's algorithm|जॉनसन-डिजिस्ट्रा]] [[Fibonacci heap|फिबोनैकी  हीप के साथ]]|| ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;log&nbsp;''V'')) || {{harvnb|फ्रेडमन|तजरन|1984}}, {{harvnb| फ्रेडमन |तजरन|1987}}, {{harvnb|जॉनसन|1977}}के बाद अनुकूलित
|-
|-
| <math>\mathbb{N}</math> || [[Johnson's algorithm|Johnson's technique]] applied to Dial's algorithm<ref name="dial69" /> || ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;''L'')) || {{harvnb|Dial|1969}}, adapted after {{harvnb|Johnson|1977}}
| <math>\mathbb{N}</math> || [[Johnson's algorithm|जॉनसन-]]<nowiki/>डायल अल्गोरिथिम पर लागू तकनीक<ref name="dial69">{{cite journal
  | last = Dial | first = Robert B.
  | title = Algorithm 360: Shortest-Path Forest with Topological Ordering [H]
  | journal = Communications of the ACM
  | volume = 12
  | issue = 11
  | pages = 632–633
  | year = 1969
  | doi = 10.1145/363269.363610
  | s2cid = 6754003
| doi-access = free
  }}</ref>|| ''O''(''V''&nbsp;(''E''&nbsp;+&nbsp;''L'')) || {{harvnb|डायल |1969}}, {{harvnb|जॉनसन|1977}}के बाद अनुकूलित
|}
|}
{{expand list|date=December 2012}}




=== नकारात्मक चक्रों के साथ मनमाने वजन के साथ निर्देशित रेखांकन ===
=== नकारात्मक चक्रों के साथ इच्छानुसार भार के साथ निर्देशित रेखांकन ===
ऋणात्मक चक्र ढूँढता है या सभी शीर्षों के लिए दूरियों की गणना करता है।
ऋणात्मक चक्र अवलोकन है या प्रत्येक शीर्षों के लिए दूरियों की गणना करता है।
{| class=wikitable
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
!वेइट्स
! अल्गोरिथिम !! समय जटिलता !! लेखक
|-
|-
| <math>\mathbb{Z}</math> || Andrew V. Goldberg || <math>O(E\sqrt{V}\log{N})</math> ||
| <math>\mathbb{Z}</math> || एंड्रयू वी गोल्डबर्ग || <math>O(E\sqrt{V}\log{N})</math> ||
|}
|}


Line 134: Line 129:
=== गैर-ऋणात्मक भार के साथ समतल रेखांकन ===
=== गैर-ऋणात्मक भार के साथ समतल रेखांकन ===
{| class=wikitable
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
! वेइट्स !! अल्गोरिथिम !! समय जटिलता !! लेखक
|-
|-
| <math>\mathbb{R}_{\geq 0}</math> || || <math> O( V )</math> || {{harvnb|Henzinger|Klein|Rao|Subramanian|1997}}
| <math>\mathbb{R}_{\geq 0}</math> || || <math> O( V )</math> || {{harvnb|हैंजिनगीर |Klein|Rao|Subramanian|1997}}
|}
|}




== सभी जोड़े सबसे छोटे रास्ते ==
== प्रत्येक जोड़े सबसे छोटा मार्ग ==
ऑल-पेयर शॉर्टेस्ट पाथ प्रॉब्लम हर जोड़ी वर्टिकल के मध्य सबसे छोटा रास्ता खोजती है {{mvar|v}}, {{mvar|v'}} ग्राफ में। अनवेटेड डायरेक्टेड ग्राफ के लिए ऑल-पेयर शॉर्टेस्ट पाथ प्रॉब्लम किसके द्वारा पेश की गई थी? {{harvtxt|Shimbel|1953}}, जिन्होंने देखा कि इसे मैट्रिक्स गुणन की रैखिक संख्या द्वारा हल किया जा सकता है जिसमें कुल समय लगता है {{math|''O''(''V''<sup>4</sup>)}}.
जोड़े सबसे छोटा पथ समस्या ग्राफ में ऊर्ध्वाधर {{mvar|v}}, {{mvar|v'}} के प्रत्येक जोड़े के मध्य सबसे छोटा मार्ग का अवलोकन करती है। {{harvtxt|Shimbel|1953}} द्वारा अनिर्धारित डायरेक्टेड ग्राफ के लिए जोड़े सबसे छोटा पथ समस्या किसके द्वारा प्रस्तावित की गई थी? जिन्होंने देखा कि इसे मैट्रिक्स गुणन की रैखिक संख्या द्वारा समाधान किया जा सकता है जिसमें {{math|''O''(''V''<sup>4</sup>)}} कुल समय लगता है।  .


=== अप्रत्यक्ष ग्राफ ===
=== अप्रत्यक्ष ग्राफ ===
{| class=wikitable
{| class=wikitable
! Weights !! Time complexity !! Algorithm
!वेइट्स
! समय जटिलता !! अल्गोरिथिम
|-
|-
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''V''<sup>3</sup>)}} || [[Floyd–Warshall algorithm]]
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''V''<sup>3</sup>)}} || [[Index.php?title=Floyd–Warshall अल्गोरिथिम algorithm|फ्ल्यूड–वर्षल अल्गोरिथिम]]  
|-
|-
| <math>\{1, \infty\}</math> || <math>O(V^\omega \log V)</math> || [[Seidel's algorithm]] (expected running time)
| <math>\{1, \infty\}</math> || <math>O(V^\omega \log V)</math> || [[Seidel's algorithm|सैंडल]] [[Index.php?title=Floyd–Warshall अल्गोरिथिम algorithm|अल्गोरिथिम]]
|-
|-
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log n)^{1/2}})</math> || {{harvnb|Williams|2014}}
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log n)^{1/2}})</math> || {{harvnb|विल्लियम्स|2014}}
|-
|-
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''EV''&nbsp;log&nbsp;α(''E'',''V''))}} || {{harvnb|Pettie|Ramachandran|2002}}
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''EV''&nbsp;log&nbsp;α(''E'',''V''))}} || {{harvnb| पट्टी | रामचंद्रन |2002}}
|-
|-
| <math>\mathbb{N}</math> || {{math|''O''(''EV'')}} || {{harvnb|Thorup|1999}} applied to every vertex (requires constant-time multiplication).
| <math>\mathbb{N}</math> || {{math|''O''(''EV'')}} || {{harvnb|थोरुप |1999}} प्रत्येक शीर्ष पर लागू होता है(निरंतर-समय गुणन की आवश्यकता है).
|}
|}


Line 161: Line 157:
=== निर्देशित ग्राफ ===
=== निर्देशित ग्राफ ===
{| class=wikitable
{| class=wikitable
! Weights !! Time complexity !! Algorithm
!वेइट्स
! समय जटिलता !! अल्गोरिथिम
|-
|-
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''V''<sup>3</sup>)}} || [[Floyd–Warshall algorithm]]
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''V''<sup>3</sup>)}} || [[Floyd–Warshall algorithm|फ्ल्यूड–वर्षल अल्गोरिथिम]]
|-
|-
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log n)^{1/2}})</math> || {{harvnb|Williams|2014}}
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log n)^{1/2}})</math> || {{harvnb|विल्लियम्स|2014}}
|-
|-
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;''V'')}} || [[Johnson's algorithm|Johnson–Dijkstra]]
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;''V'')}} || [[Index.php?title=Johnson'sजॉनसनalgorithm|जॉनसन–दंतजिग]]
|-
|-
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb|Pettie|2004}}
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb|पट्टी|2004}}
|-
|-
| <math>\mathbb{N}</math> || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb|Hagerup|2000}}
| <math>\mathbb{N}</math> || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb| हाग्रुप|2000}}
|}
|}




== अनुप्रयोग ==
== अनुप्रयोग ==
[[मैपक्वेस्ट]] या [[गूगल मानचित्र]] जैसी [[वेब मैपिंग]] वेबसाइटों पर ड्राइविंग दिशाओं जैसे भौतिक स्थानों के मध्य स्वचालित रूप से दिशाओं को खोजने के लिए सबसे छोटा पथ एल्गोरिदम लागू किया जाता है। इस एप्लिकेशन के लिए तेजी से विशेष एल्गोरिदम उपलब्ध हैं।<ref>{{Cite web|title=Fast route planning|first=Peter|last=Sanders|author-link=Peter Sanders (computer scientist)|work=Google Tech Talk|date=March 23, 2009|url=https://www.youtube.com/watch?v=-0ErpE8tQbw |archive-url=https://ghostarchive.org/varchive/youtube/20211211/-0ErpE8tQbw| archive-date=2021-12-11 |url-status=live}}{{cbignore}}</ref>यदि कोई ग्राफ के रूप में गैर-नियतात्मक [[अमूर्त मशीन]] का प्रतिनिधित्व करता है, जहां कोने राज्यों एवं  किनारों का वर्णन करते हैं, तो संभव संक्रमण का वर्णन करते हैं, निश्चित लक्ष्य स्थिति तक पहुंचने के लिए विकल्पों का इष्टतम अनुक्रम खोजने के लिए, या आवश्यक समय पर कम सीमा स्थापित करने के लिए सबसे छोटा पथ एल्गोरिदम का उपयोग किया जा सकता है। किसी दिए गए राज्य तक पहुँचें उदाहरण के लिए, यदि कोने रूबिक क्यूब जैसी पहेली की अवस्थाओं का प्रतिनिधित्व करते हैं एवं प्रत्येक निर्देशित किनारा चाल या मोड़ से मेल खाता है, तो सबसे छोटा पथ एल्गोरिदम का उपयोग समाधान खोजने के लिए किया जा सकता है जो चालों की न्यूनतम संभव संख्या का उपयोग करता है।
[[मैपक्वेस्ट]] या [[गूगल मानचित्र]] जैसी [[वेब मैपिंग]] वेबसाइटों पर ड्राइविंग दिशाओं जैसे भौतिक स्थानों के मध्य स्वचालित रूप से दिशाओं को अवलोकन के लिए सबसे छोटा पथ एल्गोरिदम प्रारम्भ किया जाता है। इस एप्लिकेशन के लिए तीव्रता से विशेष एल्गोरिदम उपलब्ध हैं।<ref>{{Cite web|title=Fast route planning|first=Peter|last=Sanders|author-link=Peter Sanders (computer scientist)|work=Google Tech Talk|date=March 23, 2009|url=https://www.youtube.com/watch?v=-0ErpE8tQbw |archive-url=https://ghostarchive.org/varchive/youtube/20211211/-0ErpE8tQbw| archive-date=2021-12-11 |url-status=live}}{{cbignore}}</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>{{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> बड़ी संख्या में एल्गोरिदम हैं जो इस संपत्ति का लाभ उठाते हैं एवं यह कारण है की सामान्य ग्राफ़ पर जितना संभव हो उतना तीव्र पथ की गणना करने में सक्षम हैं।


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


सबसे तेज़ ज्ञात क्वेरी समय वाले एल्गोरिदम को हब लेबलिंग कहा जाता है एवं यह माइक्रोसेकंड के अंश में यूरोप या यूएस के सड़क नेटवर्क पर सबसे छोटे पथ की गणना करने में सक्षम है।<ref>Abraham, Ittai; Delling, Daniel; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/142356/HL-TR.pdf 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.</ref> अन्य तकनीकों का उपयोग किया गया है:
सबसे तीव्र ज्ञात क्वेरी समय वाले एल्गोरिदम को हब लेबलिंग कहा जाता है एवं यह माइक्रोसेकंड के अंश में यूरोप या यूएस के मार्ग नेटवर्क पर सबसे छोटे पथ की गणना करने में सक्षम है।<ref>Abraham, Ittai; Delling, Daniel; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/142356/HL-TR.pdf 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.</ref> अन्य  प्राद्यौगिकी का उपयोग किया गया है:


* ALT (A* खोज, लैंडमार्क एवं त्रिभुज असमानता)
* ALT (ऑल्ट) (A खोज, लैंडमार्क एवं त्रिफला असमानता)
* आर्क झंडे
* आर्क फ्लैग्स
* [[संकुचन पदानुक्रम]]
* [[संकुचन पदानुक्रम]]
* [[ट्रांजिट नोड रूटिंग]]
* [[ट्रांजिट नोड रूटिंग]]
* पहुंच-आधारित छंटाई
* पहुंच-आधारित सॉर्टिंग
* लेबलिंग
* लेबलिंग
* [[हब लेबल]]
* [[हब लेबल]]


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


सबसे छोटा एकाधिक डिस्कनेक्ट पथ <ref>{{cite journal |doi=10.1016/j.cpc.2005.01.020 |title=Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems |year=2005 |first=Martin |last=Kroger |journal=Computer Physics Communications |volume=168 |issue=3 |pages=209–232 |bibcode=2005CoPhC.168..209K }}</ref> [[पुनरावृत्ति सिद्धांत]] के ढांचे के भीतर आदिम पथ नेटवर्क का प्रतिनिधित्व है। व्यापक पथ समस्या पथ की तलाश करती है ताकि किसी भी किनारे का न्यूनतम लेबल जितना संभव हो उतना बड़ा हो।
सबसे छोटा एकाधिक पृथक पथ <ref>{{cite journal |doi=10.1016/j.cpc.2005.01.020 |title=Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems |year=2005 |first=Martin |last=Kroger |journal=Computer Physics Communications |volume=168 |issue=3 |pages=209–232 |bibcode=2005CoPhC.168..209K }}</ref> [[पुनरावृत्ति सिद्धांत]] के रूप के भीतर सर्वप्रथम पथ नेटवर्क का प्रतिनिधित्व है। व्यापक पथ समस्या पथ का अन्वेषण करती है किसी भी किनारे का न्यूनतम लेबल जितना संभव हो उतना बड़ा हो।


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


=== बाधाओं के साथ पथ ===
=== बाधाओं के साथ पथ ===
सबसे छोटी पथ समस्या के विपरीत, जिसे नकारात्मक चक्रों के बिना ग्राफ़ में बहुपद समय में हल किया जा सकता है, सबसे छोटी पथ समस्याएँ जिनमें वांछित समाधान पथ पर अतिरिक्त बाधाएँ शामिल होती हैं, उन्हें [[कंस्ट्रेन्टेड शोर्टेस्ट पाथ फर्स्ट]] कहा जाता है, एवं हल करना कठिन होता है। उदाहरण विवश लघुतम पथ समस्या है,<ref>{{cite journal |last1=Lozano |first1=Leonardo |last2=Medaglia |first2=Andrés L |title=On an exact method for the constrained shortest path problem |journal=Computers & Operations Research |date=2013 |volume=40 |issue=1 |page=378--384 |doi=10.1016/j.cor.2012.07.008 |url=https://www.sciencedirect.com/science/article/pii/S0305054812001530}}</ref> जो पथ की कुल लागत को कम करने का प्रयास करता है जबकि साथ ही किसी दिए गए थ्रेसहोल्ड के नीचे एवं मीट्रिक बनाए रखता है। यह समस्या को एनपी-पूर्ण बनाता है (ऐसी समस्याओं को डेटा के बड़े सेट के लिए कुशलता से हल करने योग्य नहीं माना जाता है, पी = एनपी समस्या देखें)। अन्य एनपी-पूर्ण उदाहरण के लिए पथ में शामिल किए जाने वाले वर्टिकल के विशिष्ट सेट की आवश्यकता होती है,<ref>{{cite journal |last1=Osanlou |first1=Kevin |last2=Bursuc |first2=Andrei |last3=Guettier |first3=Christophe |last4=Cazenave |first4=Tristan |last5=Jacopin |first5=Eric |title=Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search |journal=2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |date=2019 |page=3519--3525 |doi=10.1109/IROS40897.2019.8968113 |arxiv=2108.01036 |isbn=978-1-7281-4004-9 |s2cid=210706773 |url= https://arxiv.org/abs/2108.01036}}</ref> जो समस्या को [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) के समान बनाता है। टीएसपी सबसे छोटा रास्ता खोजने की समस्या है जो हर शीर्ष से ठीक बार गुजरता है, एवं शुरुआत में वापस आ जाता है। ग्राफ़ में सबसे लंबे पथ की समस्या भी एनपी-पूर्ण है।
अल्पतम पथ समस्या के विपरीत, जिसे नकारात्मक चक्रों के बिना ग्राफ़ में बहुपद समय में समाधान किया जा सकता है, अल्पतम पथ समस्याएँ जिनमें वांछित समाधान पथ पर अतिरिक्त बाधाएँ सम्मलित होती हैं, उन्हें [[कंस्ट्रेन्टेड शोर्टेस्ट पाथ फर्स्ट|विवश सबसे छोटा सर्वप्रथम पथ]] कहा जाता है, एवं समाधान करना कठिन होता है। उदाप्रत्येकण विवश लघुतम पथ समस्या है,<ref>{{cite journal |last1=Lozano |first1=Leonardo |last2=Medaglia |first2=Andrés L |title=On an exact method for the constrained shortest path problem |journal=Computers & Operations Research |date=2013 |volume=40 |issue=1 |page=378--384 |doi=10.1016/j.cor.2012.07.008 |url=https://www.sciencedirect.com/science/article/pii/S0305054812001530}}</ref> जो पथ की कुल व्यय को अल्प करने का प्रयास करता है जबकि साथ ही किसी दिए गए थ्रेसहोल्ड के नीचे एवं मीट्रिक बनाए रखता है। यह समस्या को एनपी-पूर्ण बनाता है (ऐसी समस्याओं को डेटा के बड़े समुच्चय के लिए कुशलता से समाधान करने योग्य नहीं माना जाता है, पी(P)=एनपी(NP) समस्या देखें)। अन्य एनपी(NP)-पूर्ण उदाप्रत्येकण के लिए पथ में सम्मलित किए जाने वाले ऊर्ध्वाधर के विशिष्ट समुच्चय की आवश्यकता होती है,<ref>{{cite journal |last1=Osanlou |first1=Kevin |last2=Bursuc |first2=Andrei |last3=Guettier |first3=Christophe |last4=Cazenave |first4=Tristan |last5=Jacopin |first5=Eric |title=Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search |journal=2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |date=2019 |page=3519--3525 |doi=10.1109/IROS40897.2019.8968113 |arxiv=2108.01036 |isbn=978-1-7281-4004-9 |s2cid=210706773 |url= https://arxiv.org/abs/2108.01036}}</ref> जो समस्या को [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) के समान बनाता है। टीएसपी सबसे छोटा मार्ग अवलोकन की समस्या है जो प्रत्येक शीर्ष से निकलता है, एवं प्रारंभ में वापस आ जाता है। ग्राफ़ में सबसे लंबे पथ की समस्या भी एनपी पूर्ण है।


=== आंशिक अवलोकनशीलता ===
=== आंशिक अवलोकनशीलता ===
[[कनाडाई यात्री समस्या]] एवं स्टोकेस्टिक शॉर्टेस्ट पाथ प्रॉब्लम सामान्यीकरण हैं जहां या तो ग्राफ मूवर को पूरी तरह से ज्ञात नहीं है, समय के साथ बदलता है, या जहां क्रियाएं (ट्रैवर्सल) संभाव्य हैं। <ref>{{cite journal |last1=Bar-Noy |first1=Amotz |last2=Schieber |first2=Baruch |title=The canadian traveller problem |journal=Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms |date=1991 |pages=261–270 |citeseerx=10.1.1.1088.3015 }}</ref> <ref>{{cite journal |last1=Nikolova |first1=Evdokia |last2=Karger |first2=David R |title=Route planning under uncertainty: the Canadian traveller problem |journal=Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI) |page=969--974 |url=https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
[[कनाडाई यात्री समस्या]] एवं स्टोकेस्टिक लघुतम मार्ग समस्या सामान्यीकरण हैं जहां या तो ग्राफ को पूर्ण प्रकार से ज्ञात नहीं है, समय के साथ परिवर्तित है, या जहां क्रियाएं (ट्रैवर्सल) संभाव्य हैं। <ref>{{cite journal |last1=Bar-Noy |first1=Amotz |last2=Schieber |first2=Baruch |title=The canadian traveller problem |journal=Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms |date=1991 |pages=261–270 |citeseerx=10.1.1.1088.3015 }}</ref> <ref>{{cite journal |last1=Nikolova |first1=Evdokia |last2=Karger |first2=David R |title=Route planning under uncertainty: the Canadian traveller problem |journal=Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI) |page=969--974 |url=https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.aaai.org/Papers/AAAI/2008/AAAI08-154.pdf |archive-date=2022-10-09 |url-status=live}}</ref>




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


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


* बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र का पता लगाने के लिए किया जा सकता है <math>O(|V||E|)</math>.
* बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र को ज्ञात करने के लिए किया जा सकता है <math>O(|V||E|)</math>.
* चर्कास्की एवं गोल्डबर्ग<ref>{{Cite journal |last1=Cherkassky |first1=Boris V. |last2=Goldberg |first2=Andrew V. |date=1999-06-01 |title=Negative-cycle detection algorithms |url=https://doi.org/10.1007/s101070050058 |journal=Mathematical Programming |language=en |volume=85 |issue=2 |pages=277–311 |doi=10.1007/s101070050058 |s2cid=79739 |issn=1436-4646}}</ref> नकारात्मक चक्र का पता लगाने के लिए कई अन्य एल्गोरिदम का सर्वेक्षण करें।
* चर्कास्की एवं गोल्डबर्ग<ref>{{Cite journal |last1=Cherkassky |first1=Boris V. |last2=Goldberg |first2=Andrew V. |date=1999-06-01 |title=Negative-cycle detection algorithms |url=https://doi.org/10.1007/s101070050058 |journal=Mathematical Programming |language=en |volume=85 |issue=2 |pages=277–311 |doi=10.1007/s101070050058 |s2cid=79739 |issn=1436-4646}}</ref> नकारात्मक चक्र को ज्ञात करने के लिए कई अन्य एल्गोरिदम का सर्वेक्षण करें।


== सेमीरिंग पर सामान्य बीजगणितीय रूपरेखा: बीजगणितीय पथ समस्या ==
== सेमीरिंग पर सामान्य बीजगणितीय रूपरेखा: बीजगणितीय पथ समस्या ==
कई समस्याओं को पथ के साथ जोड़ने एवं न्यूनतम लेने की कुछ उपयुक्त रूप से प्रतिस्थापित धारणाओं के लिए सबसे छोटे पथ के रूप में तैयार किया जा सकता है। इनके लिए सामान्य दृष्टिकोण दो परिचालनों को [[मोटी हो जाओ]] के रूप में माना जाता है। सेमिरिंग गुणन पथ के साथ किया जाता है, एवं जोड़ पथों के मध्य होता है। इस सामान्य ढाँचे को [[बीजगणितीय पथ समस्या]] के रूप में जाना जाता है।<ref name="Pair1966">{{cite conference |first = Claude | last = Pair
कई समस्याओं को पथ के साथ जोड़ने एवं न्यूनतम लेने की कुछ उपयुक्त रूप से प्रतिस्थापित धारणाओं के लिए सबसे छोटे पथ के रूप में तैयार किया जा सकता है। इनके लिए सामान्य दृष्टिकोण दो परिचालनों को [[मोटी हो जाओ|सेमिरिंग]] के रूप में माना जाता है। सेमिरिंग गुणन पथ के साथ किया जाता है, एवं जोड़ पथों के मध्य होता है। इस सामान्य रूप को [[बीजगणितीय पथ समस्या]] के रूप में जाना जाता है।<ref name="Pair1966">{{cite conference |first = Claude | last = Pair
| chapter =  Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)
| chapter =  Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)
| title = Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium)
| title = Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium)
Line 238: Line 235:
| publisher = Dunod (Paris)
| publisher = Dunod (Paris)
| year = 1971
| year = 1971
}}</ref><ref name="BarasTheodorakopoulos2010">{{cite book |first1=John |last1=Baras |first2=George |last2=Theodorakopoulos |title=Path Problems in Networks|url=https://books.google.com/books?id=fZJeAQAAQBAJ&pg=PA9|date=4 April 2010|publisher=Morgan & Claypool Publishers|isbn=978-1-59829-924-3|pages=9–}}</ref>इस तरह के बीजगणितीय संरचनाओं पर रैखिक प्रणालियों को हल करने के रूप में अधिकांश क्लासिक शॉर्टेस्ट-पाथ एल्गोरिदम (एवं नए) तैयार किए जा सकते हैं। हाल ही में, [[मूल्यांकन बीजगणित]] के बैनर तले इन (एवं बहुत कम स्पष्ट रूप से संबंधित समस्याओं) को हल करने के लिए एवं अधिक सामान्य रूपरेखा विकसित की गई है।.<ref name="PoulyKohlas2012">{{cite book |first1=Marc |last1=Pouly |first2=Jürg |last2=Kohlas |title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|at=Chapter 6. Valuation Algebras for Path Problems}}</ref>
}}</ref><ref name="BarasTheodorakopoulos2010">{{cite book |first1=John |last1=Baras |first2=George |last2=Theodorakopoulos |title=Path Problems in Networks|url=https://books.google.com/books?id=fZJeAQAAQBAJ&pg=PA9|date=4 April 2010|publisher=Morgan & Claypool Publishers|isbn=978-1-59829-924-3|pages=9–}}</ref>इस प्रकार के बीजगणितीय संरचनाओं पर रैखिक प्रणालियों को समाधान  करने के रूप में अधिकांश क्लासिक लघुतम मार्ग एल्गोरिदम (एवं नए) तैयार किए जा सकते हैं। वर्तमान में, [[मूल्यांकन बीजगणित]] के बैनर के अंतर्गत (एवं अधिक अल्प स्पष्ट रूप से संबंधित समस्याओं) को समाधान करने के लिए एवं अधिक सामान्य रूपरेखा विकसित की गई है।.<ref name="PoulyKohlas2012">{{cite book |first1=Marc |last1=Pouly |first2=Jürg |last2=Kohlas |title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|at=Chapter 6. Valuation Algebras for Path Problems}}</ref>




== स्टोकेस्टिक टाइम-डिपेंडेंट नेटवर्क्स में सबसे छोटा रास्ता ==
== स्टोकेस्टिक टाइम-डिपेंडेंट नेटवर्क्स में सबसे छोटा मार्ग ==
वास्तविक जीवन की स्थितियों में, परिवहन नेटवर्क सामान्यतः स्टोकेस्टिक एवं समय पर निर्भर होता है। वास्तव में, यात्री प्रतिदिन लिंक पर यात्रा कर रहा है, न केवल यात्रा की मांग (मूल-गंतव्य मैट्रिक्स) में उतार-चढ़ाव के कारण, किंतु कार्य क्षेत्र, खराब मौसम की स्थिति, दुर्घटनाओं एवं वाहन के टूटने जैसी घटनाओं के कारण भी उस लिंक पर यात्रा के अलग-अलग समय का अनुभव कर सकता है। नतीजतन, स्टोकास्टिक टाइम-डिपेंडेंट (एसटीडी) नेटवर्क निर्धारिती की तुलना में वास्तविक सड़क नेटवर्क का अधिक यथार्थवादी प्रतिनिधित्व है।<ref>Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.</ref><ref>{{cite journal |last1=Rajabi-Bahaabadi |first1=Mojtaba |first2=Afshin |last2=Shariat-Mohaymany |first3=Mohsen |last3=Babaei |first4=Chang Wook |last4=Ahn |title=Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm |journal=Expert Systems with Applications |date=2015 |volume=42 |issue=12|pages=5056–5064 |doi=10.1016/j.eswa.2015.02.046 }}</ref>पिछले दशक के दौरान काफी प्रगति के बावजूद, यह एक विवादास्पद प्रश्न बना हुआ है कि स्टोकास्टिक सड़क नेटवर्क में इष्टतम पथ को कैसे परिभाषित एवं पहचाना जाना चाहिए। दूसरे शब्दों में, अनिश्चितता के तहत इष्टतम पथ की कोई अनूठी परिभाषा नहीं है। इस प्रश्न का संभावित एवं सामान्य उत्तर न्यूनतम अपेक्षित यात्रा समय के साथ रास्ता खोजना है। इस दृष्टिकोण का उपयोग करने का मुख्य लाभ यह है कि नियतात्मक नेटवर्क के लिए पेश किए गए कुशल लघुतम पथ एल्गोरिदम को स्टोकेस्टिक नेटवर्क में न्यूनतम अपेक्षित यात्रा समय के साथ पथ की पहचान करने के लिए आसानी से नियोजित किया जा सकता है। चूँकि, इस दृष्टिकोण द्वारा पहचाना गया परिणामी इष्टतम पथ विश्वसनीय नहीं हो सकता है, क्योंकि यह दृष्टिकोण यात्रा समय परिवर्तनशीलता को संबोधित करने में विफल रहता है। इस समस्या से निपटने के लिए कुछ शोधकर्ता इसके अपेक्षित मूल्य के अतिरिक्त यात्रा के समय के वितरण का उपयोग करते हैं, इसलिए वे [[गतिशील प्रोग्रामिंग]] एवं दिज्क्स्ट्रा के एल्गोरिथ्म जैसे विभिन्न अनुकूलन विधियों का उपयोग करके कुल यात्रा समय का संभाव्यता वितरण पाते हैं।<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Finding shortest path in a combined exponential – gamma probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=1|pages=25–37 |doi=10.1504/IJOR.2014.064020 }}</ref> संभाव्य चाप लंबाई वाले नेटवर्क में सबसे छोटा रास्ता खोजने के लिए ये विधियां [[स्टोचैस्टिक अनुकूलन]], विशेष रूप से स्टोकास्टिक गतिशील प्रोग्रामिंग का उपयोग करती हैं।<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=2|pages=143–154 |doi=10.1504/IJOR.2014.064541 }}</ref> परिवहन अनुसंधान साहित्य में यात्रा समय की विश्वसनीयता की अवधारणा को यात्रा के समय की परिवर्तनशीलता के साथ दूसरे के स्थान पर उपयोग किया जाता है, जिससे, सामान्य तौर पर, यह कहा जा सके कि यात्रा समय में परिवर्तनशीलता जितनी अधिक होगी, विश्वसनीयता उतनी ही कम होगी, एवं इसके विपरीत।
वास्तविक जीवन की स्थितियों में, परिवहन नेटवर्क सामान्यतः स्टोकेस्टिक एवं समय पर निर्भर होता है। वास्तव में, यात्री प्रतिदिन लिंक पर यात्रा कर रहा है, न केवल यात्रा की आवश्यकता अनुसार (मूल-गंतव्य मैट्रिक्स) में उतार-चढ़ाव के कारण, किंतु कार्य क्षेत्र, दुर्गति मौसम की स्थिति, दुर्घटनाओं एवं वाहन के टूटने जैसी घटनाओं के कारण भी उस लिंक पर यात्रा के भिन्न-भिन्न समय का अनुभव कर सकता है। परिणाम स्वरुप, स्टोकास्टिक टाइम-डिपेंडेंट (एसटीडी) नेटवर्क निर्धारिती की तुलना में वास्तविक मार्ग नेटवर्क का अधिक यथार्थवादी प्रतिनिधित्व है।<ref>Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.</ref><ref>{{cite journal |last1=Rajabi-Bahaabadi |first1=Mojtaba |first2=Afshin |last2=Shariat-Mohaymany |first3=Mohsen |last3=Babaei |first4=Chang Wook |last4=Ahn |title=Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm |journal=Expert Systems with Applications |date=2015 |volume=42 |issue=12|pages=5056–5064 |doi=10.1016/j.eswa.2015.02.046 }}</ref>पिछले दशक के समय अधिक प्रगति के अतिरिक्त, यह विवादास्पद प्रश्न बना हुआ है कि स्टोकास्टिक मार्ग नेटवर्क में इष्टतम पथ को कैसे परिभाषित एवं पहचाना जाना चाहिए। दूसरे शब्दों में, अनिश्चितता के अंतर्गत इष्टतम पथ की कोई अदभूत परिभाषा नहीं है। इस प्रश्न का संभावित एवं सामान्य उत्तर न्यूनतम अपेक्षित यात्रा समय के साथ मार्ग का अवलोकन करना है। इस दृष्टिकोण का उपयोग करने का मुख्य लाभ यह है कि नियतात्मक नेटवर्क के लिए प्रस्तावित किए गए कुशल लघुतम पथ एल्गोरिदम को स्टोकेस्टिक नेटवर्क में न्यूनतम अपेक्षित यात्रा समय के साथ पथ की पहचान करने के लिए सरलता से नियोजित किया जा सकता है। चूँकि, इस दृष्टिकोण द्वारा पहचाना गया परिणामी इष्टतम पथ विश्वसनीय नहीं हो सकता है, क्योंकि यह दृष्टिकोण यात्रा समय परिवर्तनशीलता को संबोधित करने में विफल रहता है। इस समस्या के निवारण के लिए कुछ शोधकर्ता इसके अपेक्षित मूल्य के अतिरिक्त यात्रा के समय के वितरण का उपयोग करते हैं, इसलिए वे [[गतिशील प्रोग्रामिंग]] एवं दिज्क्स्ट्रा के एल्गोरिथ्म जैसे विभिन्न अनुकूलन विधियों का उपयोग करके कुल यात्रा समय का संभाव्यता वितरण पाते हैं।<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Finding shortest path in a combined exponential – gamma probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=1|pages=25–37 |doi=10.1504/IJOR.2014.064020 }}</ref> संभाव्य चाप लंबाई वाले नेटवर्क में सबसे छोटा मार्ग अवलोकन के लिए ये विधियां [[स्टोचैस्टिक अनुकूलन]], विशेष रूप से स्टोकास्टिक गतिशील प्रोग्रामिंग का उपयोग करती हैं।<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=2|pages=143–154 |doi=10.1504/IJOR.2014.064541 }}</ref> परिवहन अनुसंधान साहित्य में यात्रा समय की विश्वसनीयता की अवधारणा को यात्रा के समय की परिवर्तनशीलता के साथ दूसरे के स्थान पर उपयोग किया जाता है, जिससे, सामान्यतः यह कहा जा सके कि यात्रा समय में परिवर्तनशीलता जितनी अधिक होगी, विश्वसनीयता उतनी ही अल्प एवं इसके विपरीत होगी।


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


== यह भी देखें ==
== यह भी देखें ==
* [[द्विदिश खोज]], एल्गोरिथ्म जो निर्देशित ग्राफ पर दो शीर्षों के मध्य सबसे छोटा रास्ता खोजता है
* [[द्विदिश खोज]], एल्गोरिथ्म जो निर्देशित ग्राफ पर दो शीर्षों के मध्य सबसे छोटा मार्ग का अवलोकन करना है
* यूक्लिडियन सबसे छोटा रास्ता
* यूक्लिडियन सबसे छोटा मार्ग
* [[प्रवाह नेटवर्क]]
* [[प्रवाह नेटवर्क]]
* [[K सबसे छोटा पथ रूटिंग]]
* [[K सबसे छोटा पथ रूटिंग]]
Line 380: Line 377:


{{Authority control}}
{{Authority control}}
[[Category: नेटवर्क सिद्धांत]] [[Category: ग्राफ दूरी]] [[Category: बहुपद-समय की समस्याएं]] [[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]] [[Category: एडजर डब्ल्यू डिज्कस्ट्रा]]


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 errors]]
[[Category:CS1 maint]]
[[Category:Created On 17/02/2023]]
[[Category:Created On 17/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एडजर डब्ल्यू डिज्कस्ट्रा]]
[[Category:ग्राफ दूरी]]
[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
[[Category:नेटवर्क सिद्धांत]]
[[Category:बहुपद-समय की समस्याएं]]

Latest revision as of 10:22, 7 March 2023

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

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

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

परिभाषा

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

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

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

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

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

  • एकल-स्रोत लघुतम पथ समस्या, जिसमें हमें किसी स्रोत शीर्ष 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
डिजिस्ट्रा अल्गोरिथिम सूची के साथ लेजोरक 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] जो पथ की कुल व्यय को अल्प करने का प्रयास करता है जबकि साथ ही किसी दिए गए थ्रेसहोल्ड के नीचे एवं मीट्रिक बनाए रखता है। यह समस्या को एनपी-पूर्ण बनाता है (ऐसी समस्याओं को डेटा के बड़े समुच्चय के लिए कुशलता से समाधान करने योग्य नहीं माना जाता है, पी(P)=एनपी(NP) समस्या देखें)। अन्य एनपी(NP)-पूर्ण उदाप्रत्येकण के लिए पथ में सम्मलित किए जाने वाले ऊर्ध्वाधर के विशिष्ट समुच्चय की आवश्यकता होती है,[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.