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

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

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

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

परिभाषा

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

दो शीर्ष आसन्न होते हैं जब वे दोनों उभयनिष्ठ किनारे पर आपतित होते हैं। अप्रत्यक्ष ग्राफ में पथ शीर्षों का क्रम है।$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}$ चर हैं; यहां नंबरिंग अनुक्रम में स्थिति से संबंधित है एवं ऊर्ध्वाधर के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)

$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) प्राप्त किये जाते है।

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

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

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

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

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

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

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

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

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

वेइट्स	अल्गोरिथिम	समय जटिलता	लेखक
$\mathbb {R}$		$O(V^{2}EL)$	फोर्ड 1956
$\mathbb {R}$	बेल्लम फोर्ड अल्गोरिथिम	$O(VE)$	सिम्बल 1955, बेल्लम 1958, मूर 1959
$\mathbb {R}$		$O(V^{2}\log {V})$	दंतजिग 1960
$\mathbb {R}$	डिजिस्ट्रा अल्गोरिथिम सूची के साथ	$O(V^{2})$	लेजोरक et al. 1957, डिजिस्ट्रा 1959, मिन्टी (देखो पोलक & विएबैंसों 1960), वव्हिटिंग & हीलिएर 1960
$\mathbb {R}$	डिजिस्ट्रा अल्गोरिथिम के साथ बाइनरी हीप	$O((E+V)\log {V})$	जॉनसन 1977
$\mathbb {R}$	डिजिस्ट्रा अल्गोरिथिम के साथ फिबोनैकी हीप	$O(E+V\log {V})$	फेडमैन & तजरन 1984, फेडमैन & तजरन 1987
$\mathbb {N}$	डायल अल्गोरिथिम (डिजिस्ट्रा अल्गोरिथिम using a bucket queue with L buckets)	$O(E+LV)$	डायल 1969
		$O(E\log {\log {L}})$	जॉनसन 1981, कार्ल्सोन & पोब्लेट 1983
	गबोस अल्गोरिथिम	$O(E\log _{E/V}L)$	गाबो 1983, गाबो 1985
		$O(E+V{\sqrt {\log {L}}})$	आहूजा et al. 1990
	थोरुप	$O(E+V\log {\log {V}})$	थोरुप 2004

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

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

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

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

वेइट्स	अल्गोरिथिम	समय जटिलता	लेखक
$\mathbb {Z}$	एंड्रयू वी गोल्डबर्ग	$O(E{\sqrt {V}}\log {N})$

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

वेइट्स	अल्गोरिथिम	समय जटिलता	लेखक
$\mathbb {R} _{\geq 0}$		$O(V)$	हैंजिनगीर et al. 1997

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

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

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

वेइट्स	समय जटिलता	अल्गोरिथिम
$\mathbb {R}$+	O(V3)	फ्ल्यूड–वर्षल अल्गोरिथिम
$\{1,\infty \}$	$O(V^{\omega }\log V)$	सैंडल अल्गोरिथिम
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log n)^{1/2}})$	विल्लियम्स 2014
$\mathbb {R}$+	O(EV log α(E,V))	पट्टी & रामचंद्रन 2002
$\mathbb {N}$	O(EV)	थोरुप 1999 प्रत्येक शीर्ष पर लागू होता है(निरंतर-समय गुणन की आवश्यकता है).

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

वेइट्स	समय जटिलता	अल्गोरिथिम
$\mathbb {R}$ (no negative cycles)	O(V3)	फ्ल्यूड–वर्षल अल्गोरिथिम
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log n)^{1/2}})$	विल्लियम्स 2014
$\mathbb {R}$ (no negative cycles)	O(EV + V2 log V)	जॉनसन–दंतजिग
$\mathbb {R}$ (no negative cycles)	O(EV + V2 log log V)	पट्टी 2004
$\mathbb {N}$	O(EV + V2 log log V)	हाग्रुप 2000

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र को ज्ञात करने के लिए किया जा सकता है $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.