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

Revision as of 22:50, 28 February 2023

भारित निर्देशित ग्राफ़ में शीर्ष 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(V²)	दिज्क्स्ट्रा 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)$ मनमाने ढंग से भारित डीएजी में समाधान कर सकता है।^[1]

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

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

वेइट्स	अल्गोरिथिम	समय जटिलता	लेखक
$\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²EL)	फोर्ड 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}$	जॉनसन-डायल अल्गोरिथिम पर लागू तकनीक^[2]	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 4)$ .

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

↑ Cormen et al. 2001, p. 655
↑ 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.
↑ Sanders, Peter (March 23, 2009). "Fast route planning". Google Tech Talk. Archived from the original on 2021-12-11.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ 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)
↑ Derniame, Jean Claude; Pair, Claude (1971). Problèmes de cheminement dans les graphes (Path Problems in Graphs). Dunod (Paris).
↑ Baras, John; Theodorakopoulos, George (4 April 2010). Path Problems in Networks. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.
↑ 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.
↑ Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
↑ 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.
↑ 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.
↑ 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.

ग्रन्थसूची

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.

[1] Cormen et al. 2001, p. 655

[dial69-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.

[Pair1966-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).

[BarasTheodorakopoulos2010-15] Baras, John; Theodorakopoulos, George (4 April 2010). Path Problems in Networks. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.

[PoulyKohlas2012-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

@@ Line 7: / Line 7: @@
 == परिभाषा ==
-रेखांकन के लिए सबसे छोटी पथ समस्या को परिभाषित किया जा सकता है चाहे वह अप्रत्यक्ष, निर्देशित या [[मिश्रित ग्राफ]] हो। यह यहाँ अप्रत्यक्ष रेखांकन के लिए परिभाषित किया गया है; निर्देशित रेखांकन के लिए पथ की परिभाषा आवश्यकता है कि क्रमिक शीर्षों को उपयुक्त निर्देशित किनारे से जोड़ा जाए।
+रेखांकन के लिए सबसे छोटी पथ समस्या को परिभाषित किया जा सकता है चाहे वह अप्रत्यक्ष, निर्देशित या [[मिश्रित ग्राफ]] हो। यह अप्रत्यक्ष रेखांकन के लिए परिभाषित किया गया है; निर्देशित रेखांकन के लिए पथ की परिभाषा के लिए आवश्यक है कि निरंतर कोने उपयुक्त निर्देशित किनारे से जुड़े हों।
-दो शीर्ष आसन्न होते हैं जब वे दोनों उभयनिष्ठ किनारे पर आपतित होते हैं। पथ (ग्राफ सिद्धांत) अप्रत्यक्ष ग्राफ में वर्टिकल का क्रम है <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>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>v_1</math> को <math>v_n</math>.
-( <math>v_i</math> चर हैं; यहां उनकी नंबरिंग अनुक्रम में उनकी स्थिति से संबंधित है एवं वर्टिकल के किसी भी कैननिकल लेबलिंग से संबंधित होने की आवश्यकता नहीं है।)
-<math>e_{i, j}</math> दोनों के लिए किनारे की घटना हो <math>v_i</math> एवं  <math>v_j</math>हो। दिया गया फंक्शन (गणित) रियल फंक्शन है। रियल-वैल्यूड वेट फंक्शन <math>f: E \rightarrow \mathbb{R}</math>, एवं  अप्रत्यक्ष (सरल) ग्राफ <math>G</math>, से सबसे छोटा रास्ता <math>v</math> को <math>v'</math> मार्ग है <math>P = ( v_1, v_2, \ldots, v_n )</math> है, (जहाँ <math>v_1 = v</math> एवं  <math>v_n = v'</math>) वह सब संभव है <math>n</math> योग को अल्प करता है <math>\sum_{i =1}^{n-1} f(e_{i, i+1}).</math> जब ग्राफ़ में प्रत्येक किनारे का इकाई भार होता है या <math>f: E \rightarrow \{1\}</math>, यह सबसे अल्प किनारों वाला रास्ता अवलोकनके समान है।
+( <math>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) एल्गोरिथ्म प्रत्येक नोड पर अतिरिक्त संभाव्य भार के साथ सबसे छोटी स्टोकेस्टिक पथ समस्या का समाधान करता है।
-अतिरिक्त एल्गोरिदम एवं संबद्ध मूल्यांकन में {{harvtxt|चर्कास्की|गोल्डबर्ग|रेडज़िक |1996}}.पाया जा सकता है।
+अतिरिक्त एल्गोरिदम एवं संबद्ध मूल्यांकन में {{harvtxt|चर्कास्की|गोल्डबर्ग|रेडज़िक |1996}}.प्राप्त किये जाते है।
 == एकल-स्रोत सबसे छोटा पथ ==
@@ Line 59: / Line 59: @@
 === निर्देशित विश्वकोश रेखांकन (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>
@@ Line 139: / Line 139: @@
 == सभी जोड़े सबसे छोटे रास्ते ==
-ऑल-पेयर शॉर्टेस्ट पाथ प्रॉब्लम प्रत्येक जोड़ी वर्टिकल के मध्य सबसे छोटा रास्ता खोजती है {{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>)}}.
 === अप्रत्यक्ष ग्राफ ===
@@ Line 180: / Line 180: @@
 [[संगणक संजाल]] या [[दूरसंचार नेटवर्क]] मानसिकता में, इस सबसे छोटी पथ समस्या को कभी-कभी न्यूनतम-विलंब पथ समस्या कहा जाता है एवं सामान्यतः व्यापक पथ समस्या से जुड़ा होता है। उदाप्रत्येकण के लिए, एल्गोरिथ्म सबसे छोटा (न्यूनतम-विलंब) चौड़ा पथ, या सबसे छोटा (न्यूनतम-विलंब) पथ खोज सकता है।
-अधिक प्रकाशमय अनुप्रयोग छह डिग्री के अलगाव का खेल है जो ही फिल्म में दिखाई देने वाले फिल्मी सितारों की तरह रेखांकन में सबसे छोटा रास्ता अवलोकनकी कोशिश करता है।
+अधिक प्रकाशमय अनुप्रयोग छह डिग्री के अलगाव का खेल है जो ही फिल्म में दिखाई देने वाले फिल्मी सितारों की तरह रेखांकन में सबसे छोटा मार्ग अवलोकनकी कोशिश करता है।
 संचालन अनुसंधान में अक्सर अध्ययन किए जाने वाले अन्य अनुप्रयोगों में संयंत्र एवं सुविधा लेआउट,[[रोबोटिक|रोबोटिक्स]], परिवहन एवं बहुत [[बड़े पैमाने पर एकीकरण]] डिजाइन शामिल हैं।<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>
@@ Line 201: / Line 201: @@
 == संबंधित समस्याएं ==
-[[कम्प्यूटेशनल ज्यामिति]] में सबसे छोटी पथ समस्याओं के लिए, [[यूक्लिडियन सबसे छोटा रास्ता]] देखें।
+[[कम्प्यूटेशनल ज्यामिति]] में सबसे छोटी पथ समस्याओं के लिए, [[यूक्लिडियन सबसे छोटा रास्ता|यूक्लिडियन सबसे छोटा]] मार्ग देखें।
 सबसे छोटा एकाधिक डिस्कनेक्ट पथ <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> [[पुनरावृत्ति सिद्धांत]] के ढांचे के भीतर आदिम पथ नेटवर्क का प्रतिनिधित्व है। व्यापक पथ समस्या पथ की तलाश करती है चुकीं किसी भी किनारे का न्यूनतम लेबल जितना संभव हो उतना बड़ा हो।
@@ Line 208: / Line 208: @@
 === बाधाओं के साथ पथ ===
-सबसे छोटी पथ समस्या के विपरीत, जिसे नकारात्मक चक्रों के बिना ग्राफ़ में बहुपद समय में हल किया जा सकता है, सबसे छोटी पथ समस्याएँ जिनमें वांछित समाधान पथ पर अतिरिक्त बाधाएँ शामिल होती हैं, उन्हें [[कंस्ट्रेन्टेड शोर्टेस्ट पाथ फर्स्ट]] कहा जाता है, एवं  हल करना कठिन होता है। उदाप्रत्येकण विवश लघुतम पथ समस्या है,<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> जो पथ की कुल लागत को अल्प करने का प्रयास करता है जबकि साथ ही किसी दिए गए थ्रेसहोल्ड के नीचे एवं मीट्रिक बनाए रखता है। यह समस्या को एनपी-पूर्ण बनाता है (ऐसी समस्याओं को डेटा के बड़े सेट के लिए कुशलता से समाधान  करने योग्य नहीं माना जाता है, पी = एनपी समस्या देखें)। अन्य एनपी-पूर्ण उदाप्रत्येकण के लिए पथ में शामिल किए जाने वाले ऊर्ध्वाधर के विशिष्ट सेट की आवश्यकता होती है,<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> जो समस्या को [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) के समान बनाता है। टीएसपी सबसे छोटा मार्ग अवलोकनकी समस्या है जो प्रत्येक शीर्ष से ठीक बार गुजरता है, एवं शुरुआत में वापस आ जाता है। ग्राफ़ में सबसे लंबे पथ की समस्या भी एनपी-पूर्ण है।
 === आंशिक अवलोकनशीलता ===
@@ Line 215: / Line 215: @@
 === रणनीतिक सबसे छोटा रास्ता ===
-कभी-कभी, किसी ग्राफ के किनारों में व्यक्तित्व होते हैं: प्रत्येक किनारे का अपना स्वार्थ होता है। उदाप्रत्येकण संचार नेटवर्क है, जिसमें प्रत्येक किनारा कंप्यूटर है जो संभवतः अलग व्यक्ति का है। अलग-अलग कंप्यूटरों में अलग-अलग संचरण गति होती है, इसलिए नेटवर्क के प्रत्येक किनारे का संख्यात्मक भार होता है जो संदेश को प्रसारित करने के लिए मिलीसेकंड की संख्या के बराबर होता है। हमारा लक्ष्य अल्प से अल्प संभव समय में नेटवर्क में दो बिंदुओं के मध्य संदेश भेजना है। यदि हम प्रत्येक कंप्यूटर के प्रसारण-समय (प्रत्येक किनारे का वजन) को जानते हैं, तो हम मानक लघुतम-पथ एल्गोरिथम का उपयोग कर सकते हैं। यदि हम प्रसारण समय नहीं जानते हैं, तो हमें प्रत्येक कंप्यूटर से उसका प्रसारण समय बताने के लिए कहना होगा। लेकिन, कंप्यूटर स्वार्थी हो सकते हैं: कंप्यूटर हमें बता सकता है कि इसका प्रसारण समय बहुत लंबा है, चुकीं हम इसे अपने संदेशों से परेशान न करें। इस समस्या का संभावित समाधान विक्रे-क्लार्क-ग्रोव्स मैकेनिज्म सबसे तेज़ रास्तों का उपयोग करना है, जो कंप्यूटरों को उनके वास्तविक वजन को प्रकट करने के लिए  प्रोत्साहन देता है।
+कभी-कभी, किसी ग्राफ के किनारों में व्यक्तित्व होते हैं: प्रत्येक किनारे का अपना स्वार्थ होता है। उदाप्रत्येकण संचार नेटवर्क है, जिसमें प्रत्येक किनारा कंप्यूटर है जो संभवतः भिन्न व्यक्ति का है। अलग-भिन्न कंप्यूटरों में अलग-भिन्न संचरण गति होती है, इसलिए नेटवर्क के प्रत्येक किनारे का संख्यात्मक भार होता है जो संदेश को प्रसारित करने के लिए मिलीसेकंड की संख्या के बराबर होता है। हमारा लक्ष्य अल्प से अल्प संभव समय में नेटवर्क में दो बिंदुओं के मध्य संदेश भेजना है। यदि हम प्रत्येक कंप्यूटर के प्रसारण-समय (प्रत्येक किनारे का वजन) को जानते हैं, तो हम मानक लघुतम-पथ एल्गोरिथम का उपयोग कर सकते हैं। यदि हम प्रसारण समय नहीं जानते हैं, तो हमें प्रत्येक कंप्यूटर से उसका प्रसारण समय बताने के लिए कहना होगा। लेकिन, कंप्यूटर स्वार्थी हो सकते हैं: कंप्यूटर हमें बता सकता है कि इसका प्रसारण समय बहुत लंबा है, चुकीं हम इसे अपने संदेशों से परेशान न करें। इस समस्या का संभावित समाधान विक्रे-क्लार्क-ग्रोव्स मैकेनिज्म सबसे तेज़ रास्तों का उपयोग करना है, जो कंप्यूटरों को उनके वास्तविक वजन को प्रकट करने के लिए  प्रोत्साहन देता है।
 === नकारात्मक चक्र पहचान ===
-कुछ मामलों में, मुख्य लक्ष्य सबसे छोटा रास्ता खोजना नहीं है, किंतु केवल यह पता लगाना है कि ग्राफ में नकारात्मक चक्र है या नहीं। इस उद्देश्य के लिए कुछ सबसे छोटे पथ एल्गोरिदम का उपयोग किया जा सकता है:
+कुछ मामलों में, मुख्य लक्ष्य सबसे छोटा मार्ग खोजना नहीं है, किंतु केवल यह पता लगाना है कि ग्राफ में नकारात्मक चक्र है या नहीं। इस उद्देश्य के लिए कुछ सबसे छोटे पथ एल्गोरिदम का उपयोग किया जा सकता है:
 * बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग समय में नकारात्मक चक्र का पता लगाने के लिए किया जा सकता है <math>O(|V||E|)</math>.
@@ Line 238: / Line 238: @@
 | publisher = Dunod (Paris)
 | 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> परिवहन अनुसंधान साहित्य में यात्रा समय की विश्वसनीयता की अवधारणा को यात्रा के समय की परिवर्तनशीलता के साथ दूसरे के स्थान पर उपयोग किया जाता है, जिससे, सामान्य तौर पर, यह कहा जा सके कि यात्रा समय में परिवर्तनशीलता जितनी अधिक होगी, विश्वसनीयता उतनी ही अल्प  एवं इसके विपरीत होगी।
 यात्रा समय की विश्वसनीयता को अधिक सटीक रूप से समझने के लिए, अनिश्चितता के तहत इष्टतम पथ के लिए दो सामान्य वैकल्पिक परिभाषाओं का सुझाव दिया गया है। कुछ लोगों ने सबसे विश्वसनीय पथ की अवधारणा पेश की है, जिसका उद्देश्य किसी दिए गए यात्रा समय बजट की तुलना में समय पर या उससे पूर्व पहुंचने की संभावना को अधिकतम करना है। अन्य, वैकल्पिक रूप से, α-विश्वसनीय पथ की अवधारणा को सामने रखते हैं, जिसके आधार पर वे समय पर आगमन की पूर्व-निर्धारित संभावना सुनिश्चित करने के लिए आवश्यक यात्रा समय बजट को अल्प करने का लक्ष्य रखते हैं।
 == यह भी देखें ==
-* [[द्विदिश खोज]], एल्गोरिथ्म जो निर्देशित ग्राफ पर दो शीर्षों के मध्य सबसे छोटा रास्ता खोजता है
+* [[द्विदिश खोज]], एल्गोरिथ्म जो निर्देशित ग्राफ पर दो शीर्षों के मध्य सबसे छोटा मार्ग खोजता है
 * यूक्लिडियन सबसे छोटा रास्ता
 * [[प्रवाह नेटवर्क]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 22:50, 28 February 2023

Contents

परिभाषा

एल्गोरिदम