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

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

$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}$	डिजिस्ट्रा अल्गोरिथिमwith list	$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* खोज, लैंडमार्क एवं त्रिभुज असमानता)
• आर्क झंडे
• संकुचन पदानुक्रम
• ट्रांजिट नोड रूटिंग
• पहुंच-आधारित छंटाई
• लेबलिंग
• हब लेबल

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

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

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

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

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

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

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

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

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

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

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

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

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