अल्पतम पथ समस्या

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

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

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

परिभाषा

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

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

होने देना $e_{i,j}$ दोनों के लिए किनारे की घटना हो $v_{i}$ एवं $v_{j}$हो। दिया गया फंक्शन (गणित) रियल फंक्शन है। रियल-वैल्यूड वेट फंक्शन $f:E\rightarrow \mathbb {R}$, एवं अप्रत्यक्ष (सरल) ग्राफ $G$, से सबसे छोटा रास्ता $v$ को $v'$ मार्ग है $P=(v_{1},v_{2},\ldots ,v_{n})$ है, (जहाँ $v_{1}=v$ एवं $v_{n}=v'$) वह सब संभव है $n$ योग को कम करता है $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ जब ग्राफ़ में प्रत्येक किनारे का इकाई भार होता है या $f:E\rightarrow \{1\}$, यह सबसे कम किनारों वाला रास्ता खोजने के समान है।

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

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

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

एल्गोरिदम

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

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

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

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

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

Weights	Time complexity	Author
$\mathbb {R}$+	O(V2)	Dijkstra 1959
$\mathbb {R}$+	O((E + V) log V)	Johnson 1977 (binary heap)
$\mathbb {R}$+	O(E + V log V)	Fredman & Tarjan 1984 (Fibonacci heap)
$\mathbb {N}$	O(E)	Thorup 1999 (requires constant-time multiplication)

भारित रेखांकन

Algorithm	Time complexity	Author
Breadth-first search	O(E + V)

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

टोपोलोजिकल सॉर्टिंग एप्लीकेशन टू शॉर्टेस्ट पाथ फाइंडिंग का उपयोग करने वाला एल्गोरिद्म समय में एकल-स्रोत शॉर्टेस्ट पाथ प्रॉब्लम को हल कर सकता है Θ(E + V) मनमाने ढंग से भारित डीएजी में।

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

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

Weights	Algorithm	Time complexity	Author
$\mathbb {R}$		$O(V^{2}EL)$	Ford 1956
$\mathbb {R}$	Bellman–Ford algorithm	$O(VE)$	Shimbel 1955, Bellman 1958, Moore 1959
$\mathbb {R}$		$O(V^{2}\log {V})$	Dantzig 1960
$\mathbb {R}$	Dijkstra's algorithm with list	$O(V^{2})$	Leyzorek et al. 1957, Dijkstra 1959, Minty (see Pollack & Wiebenson 1960), Whiting & Hillier 1960
$\mathbb {R}$	Dijkstra's algorithm with binary heap	$O((E+V)\log {V})$	Johnson 1977
$\mathbb {R}$	Dijkstra's algorithm with Fibonacci heap	$O(E+V\log {V})$	Fredman & Tarjan 1984, Fredman & Tarjan 1987
$\mathbb {N}$	Dial's algorithm (Dijkstra's algorithm using a bucket queue with L buckets)	$O(E+LV)$	Dial 1969
		$O(E\log {\log {L}})$	Johnson 1981, Karlsson & Poblete 1983
	Gabow's algorithm	$O(E\log _{E/V}L)$	Gabow 1983, Gabow 1985
		$O(E+V{\sqrt {\log {L}}})$	Ahuja et al. 1990
	Thorup	$O(E+V\log {\log {V}})$	Thorup 2004

नकारात्मक चक्रों के बिना मनमाने वजन के साथ निर्देशित रेखांकन

Weights	Algorithm	Time complexity	Author
$\mathbb {R}$		O(V 2EL)	Ford 1956
$\mathbb {R}$	Bellman–Ford algorithm	O(VE)	Shimbel 1955, Bellman 1958, Moore 1959
$\mathbb {R}$	Johnson-Dijkstra with binary heap	O(V (E + log V))	Johnson 1977
$\mathbb {R}$	Johnson-Dijkstra with Fibonacci heap	O(V (E + log V))	Fredman & Tarjan 1984, Fredman & Tarjan 1987, adapted after Johnson 1977
$\mathbb {N}$	Johnson's technique applied to Dial's algorithm	O(V (E + L))	Dial 1969, adapted after Johnson 1977

नकारात्मक चक्रों के साथ मनमाने वजन के साथ निर्देशित रेखांकन

ऋणात्मक चक्र ढूँढता है या सभी शीर्षों के लिए दूरियों की गणना करता है।

Weights	Algorithm	Time complexity	Author
$\mathbb {Z}$	Andrew V. Goldberg	$O(E{\sqrt {V}}\log {N})$

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

Weights	Algorithm	Time complexity	Author
$\mathbb {R} _{\geq 0}$		$O(V)$	Henzinger et al. 1997

सभी जोड़े सबसे छोटे रास्ते

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

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

Weights	Time complexity	Algorithm
$\mathbb {R}$+	O(V3)	Floyd–Warshall algorithm
$\{1,\infty \}$	$O(V^{\omega }\log V)$	Seidel's algorithm (expected running time)
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log n)^{1/2}})$	Williams 2014
$\mathbb {R}$+	O(EV log α(E,V))	Pettie & Ramachandran 2002
$\mathbb {N}$	O(EV)	Thorup 1999 applied to every vertex (requires constant-time multiplication).

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

Weights	Time complexity	Algorithm
$\mathbb {R}$ (no negative cycles)	O(V3)	Floyd–Warshall algorithm
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log n)^{1/2}})$	Williams 2014
$\mathbb {R}$ (no negative cycles)	O(EV + V2 log V)	Johnson–Dijkstra
$\mathbb {R}$ (no negative cycles)	O(EV + V2 log log V)	Pettie 2004
$\mathbb {N}$	O(EV + V2 log log V)	Hagerup 2000

अनुप्रयोग

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

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

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

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

सड़क नेटवर्क

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र का पता लगाने के लिए किया जा सकता है $O(|V||E|)$.
• चर्कास्की एवं गोल्डबर्ग नकारात्मक चक्र का पता लगाने के लिए कई अन्य एल्गोरिदम का सर्वेक्षण करें।

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

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

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

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

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

यह भी देखें

• द्विदिश खोज, एल्गोरिथ्म जो निर्देशित ग्राफ पर दो शीर्षों के मध्य सबसे छोटा रास्ता खोजता है
• यूक्लिडियन सबसे छोटा रास्ता
• प्रवाह नेटवर्क
• K सबसे छोटा पथ रूटिंग
• मिन-प्लस मैट्रिक्स गुणन
• पथ खोज
• सबसे छोटा पथ ब्रिजिंग
• सबसे छोटा पथ वृक्ष
• त्रिल (कई कड़ियों का पारदर्शी अंतर्संबंध)

संदर्भ

ग्रन्थसूची

• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). "Faster algorithms for the shortest path problem" (PDF). Journal of the ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589. Archived (PDF) from the original on 2022-10-09.
• Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. MR 0102435.
• Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. MR 1392160.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Single-Source Shortest Paths and All-Pairs Shortest Paths". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 580–642. ISBN 0-262-03293-7.
• Dantzig, G. B. (January 1960). "On the Shortest Route through a Network". Management Science. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.
• Ford, L. R. (1956). "Network Flow Theory". Rand Corporation. P-923. {{cite journal}}: Cite journal requires |journal= (help)
• Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
• Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
• Gabow, H. N. (1983). "Scaling algorithms for network problems". Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983) (PDF). pp. 248–258. doi:10.1109/SFCS.1983.68.
• Gabow, Harold N. (1985). "Scaling algorithms for network problems". Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016/0022-0000(85)90039-X. MR 0828519.
• Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (eds.). Improved Shortest Paths on the Word RAM. pp. 61–72. ISBN 978-3-540-67715-4. {{cite book}}: |journal= ignored (help)
• Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). "Faster Shortest-Path Algorithms for Planar Graphs". Journal of Computer and System Sciences. 55 (1): 3–23. doi:10.1006/jcss.1997.1493.
• Johnson, Donald B. (1977). "Efficient algorithms for shortest paths in sparse networks". Journal of the ACM. 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
• Altıntaş, Gökhan (2020). Exact Solutions of Shortest-Path Problems Based on Mechanical Analogies: In Connection with Labyrinths. Amazon Digital Services LLC. p. 97. ISBN 9798655831896.
• Johnson, Donald B. (December 1981). "A priority queue in which initialization and queue operations take O(log log D) time". Mathematical Systems Theory. 15 (1): 295–309. doi:10.1007/BF01786986. MR 0683047. S2CID 35703411.
• Karlsson, Rolf G.; Poblete, Patricio V. (1983). "An O(m log log D)[[Category: Templates Vigyan Ready]] algorithm for shortest paths". Discrete Applied Mathematics. 6 (1): 91–93. doi:10.1016/0166-218X(83)90104-X. MR 0700028. {{cite journal}}: URL–wikilink conflict (help)
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Moore, E. F. (1959). "The shortest path through a maze". Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285–292.
• Pettie, Seth; Ramachandran, Vijaya (2002). Computing shortest paths with comparisons and additions. pp. 267–276. ISBN 978-0-89871-513-2. {{cite book}}: |journal= ignored (help)
• Pettie, Seth (26 January 2004). "A new approach to all-pairs shortest paths on real-weighted graphs". Theoretical Computer Science. 312 (1): 47–74. doi:10.1016/s0304-3975(03)00402-x.
• Pollack, Maurice; Wiebenson, Walter (March–April 1960). "Solution of the Shortest-Route Problem—A Review". Oper. Res. 8 (2): 224–230. doi:10.1287/opre.8.2.224. Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225.
• Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. ISBN 978-3-540-20456-5. Here: vol.A, sect.7.5b, p. 103
• Shimbel, Alfonso (1953). "Structural parameters of communication networks". Bulletin of Mathematical Biophysics. 15 (4): 501–507. doi:10.1007/BF02476438.
• Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
• Thorup, Mikkel (1999). "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
• Thorup, Mikkel (2004). "Integer priority queues with decrease key in constant time and the single source shortest paths problem". Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003.
• Whiting, P. D.; Hillier, J. A. (March–June 1960). "A Method for Finding the Shortest Route through a Road Network". Operational Research Quarterly. 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
• Williams, Ryan (2014). "Faster all-pairs shortest paths via circuit complexity". Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). New York: ACM. pp. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. MR 3238994.

अग्रिम पठन

• 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.