डिक्सट्रा एल्गोरिथम की समय जटिलता (time complexity) क्या है?

एक सरल सरणी का उपयोग करने वाले एल्गोरिथम कार्यान्वयन की समय जटिलता O(V²) है, जहां V वर्टिसेस की संख्या है। बाइनरी हीप (प्राथमिकता कतार) का उपयोग इसे O((V + E) log V) तक सुधारता है, और फिबोनाची हीप का उपयोग इसे O(E + V log V) तक लाता है।

डिक्सट्रा में निर्देशित और अदिर्शित ग्राफ के बीच क्या अंतर है?

एक निर्देशित (directed) ग्राफ में, A से B तक की एक एज का अर्थ है कि आप A→B यात्रा कर सकते हैं लेकिन B→A नहीं जब तक कि कोई अलग एज न हो। एक अदिर्शित (undirected) ग्राफ में, प्रत्येक एज द्विदिश (bidirectional) होती है। डिक्सट्रा का एल्गोरिथम दोनों पर काम करता है, लेकिन सबसे छोटे रास्ते भिन्न हो सकते हैं।

डिक्सट्रा एल्गोरिथम और BFS में क्या अंतर है?

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

डिक्सट्रा सबसे छोटा रास्ता कैलकुलेटर

भारित ग्राफ · स्रोत से सबसे छोटी दूरियां · स्टेप-बाय-स्टेप एल्गोरिथम ट्रेस · पथ विज़ुअलाइज़ेशन

इनपुट प्रकार:

ग्राफ प्रकार:

एज — प्रति पंक्ति एक: From To Weight

उदाहरण: A B 5 = A से B तक 5 भार वाली एक एज। नोड नाम अक्षर या संख्याएं हो सकते हैं।

स्रोत नोड (Source Node)

लक्ष्य नोड (वैकल्पिक)

त्वरित उदाहरण (Quick Examples)

सरल नेटवर्क

5 नोड · 7 एज · अदिशित

शहर की सड़कें

8 नोड · निर्देशित · S → T

क्लासिक ग्राफ

6 नोड · अदिशित · स्रोत 1

सबसे छोटी दूरी तालिका (Shortest Distance Table)

नोड (Node)	स्रोत से दूरी	सबसे छोटा रास्ता

आसन्नता आव्यूह दृश्य (पथ किनारों को हाइलाइट किया गया है)

एल्गोरिथम स्टेप-बाय-स्टेप ट्रेस (Step-by-Step Trace)

चरण (Step)	विज़िटिंग नोड	अपडेट की गई दूरियां

डिक्सट्रा एल्गोरिथम क्या है?

डिक्सट्रा का एल्गोरिथम कंप्यूटर विज्ञान के सबसे प्रसिद्ध एल्गोरिदम में से एक है। डच कंप्यूटर वैज्ञानिक एड्सगर डब्लू. डिक्सट्रा द्वारा 1956 में आविष्कृत और 1959 में प्रकाशित, यह गैर-ऋणात्मक एज भार वाले भारित ग्राफ के लिए सिंगल-सोर्स शॉर्टेस्ट पाथ (single-source shortest path) की समस्या को हल करता है। एक शुरुआती (स्रोत) वर्टेक्स दिए जाने पर, एल्गोरिथम उस स्रोत से ग्राफ में हर दूसरे वर्टेक्स तक न्यूनतम-लागत वाले मार्ग की गणना करता है।

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

डिक्सट्रा एल्गोरिथम कैसे काम करता है

स्रोत को छोड़कर सभी दूरियों को अनंत (Infinity) पर सेट करें, स्रोत दूरी 0 पर सेट होगी।
सभी वर्टिसेस को गैर-विज़िटेड (unvisited) के रूप में चिह्नित करें। उन्हें एक अनविज़िटेड सेट में रखें।
सबसे कम अस्थायी दूरी वाले अनविज़िटेड वर्टेक्स u का चयन करें।
u के प्रत्येक अनविज़िटेड पड़ोसी v के लिए, alt = dist[u] + weight(u, v) की गणना करें।
यदि alt < dist[v] है, तो इसे dist[v] = alt के रूप में अपडेट करें और prev[v] = u रिकॉर्ड करें।
u को विज़िटेड के रूप में चिह्नित करें (अनविज़िटेड सेट से हटा दें)।
चरण 3 से तब तक दोहराएं जब तक कि सभी वर्टिसेस विज़िट न हो जाएं या लक्ष्य नोड तक न पहुंच जाएं।

किसी भी वर्टेक्स के पथ को फिर से बनाने के लिए, लक्ष्य से स्रोत तक prev[] सरणी के माध्यम से पीछे की ओर ट्रेस करें।

डिक्सट्रा एल्गोरिथम का उदाहरण

5 नोड्स (A-E) और निम्न किनारों के साथ एक सरल नेटवर्क पर विचार करें: A-B=4, A-C=2, B-C=1, B-D=5, C-D=8, C-E=10, D-E=2। A से शुरू करते हुए:

चरण	विज़िटिंग नोड	dist[B]	dist[C]	dist[D]	dist[E]
प्रारंभ	—	∞	∞	∞	∞
1	A	4	2	∞	∞
2	C	3	2	10	12
3	B	3	2	8	12
4	D	3	2	8	10
5	E	3	2	8	10

A से अंतिम सबसे छोटी दूरियाँ: B=3 (A→C→B), C=2 (A→C), D=8 (A→C→B→D), E=10 (A→C→B→D→E)।

समय जटिलता विश्लेषण (Time Complexity Analysis)

कार्यान्वयन	समय जटिलता (Time Complexity)	स्थान जटिलता (Space)	इसके लिए सर्वश्रेष्ठ
सरणी (नाइव)	O(V²)	O(V)	सघन ग्राफ (Dense graphs)
बाइनरी हीप	O((V + E) log V)	O(V + E)	विरल ग्राफ (Sparse graphs)
फिबोनाची हीप	O(E + V log V)	O(V + E)	सैद्धांतिक रूप से इष्टतम

यह कैलकुलेटर O(V²) सरणी कार्यान्वयन का उपयोग करता है, जो 15 नोड्स तक के ग्राफ के लिए पूरी तरह से कुशल है।

डिक्सट्रा बनाम अन्य एल्गोरिदम

एल्गोरिथम	ऋणात्मक भार	एकल स्रोत	सभी जोड़े	जटिलता
डिक्सट्रा	नहीं	हाँ	नहीं	O(V² ) या O(E log V)
बेलमैन-फोर्ड	हाँ	हाँ	नहीं	O(VE)
फ्लॉइड-वॉर्शेल	हाँ	नहीं	हाँ	O(V³)
A* सर्च	नहीं	हाँ (एकल लक्ष्य)	नहीं	O(E log V) ह्यूरिस्टिक के साथ
BFS	लागू नहीं (बिना भार वाले)	हाँ	नहीं	O(V + E)

वास्तविक जीवन में अनुप्रयोग

जीपीएस नेविगेशन: सड़क नेटवर्क पर दो स्थानों के बीच सबसे तेज़ या सबसे छोटा रास्ता खोजना।
नेटवर्क राउटिंग: इंटरनेट राउटर डेटा पैकेट के लिए सर्वोत्तम पथ निर्धारित करने के लिए डिक्सट्रा के वेरिएंट (जैसे OSPF प्रोटोकॉल) का उपयोग करते हैं।
गेम पाथफाइंडिंग: वीडियो गेम में एनपीसी (NPC) पात्र डिक्सट्रा या इसके ह्यूरिस्टिक संस्करण A* का उपयोग करके नेविगेट करते हैं।
लॉजिस्टिक्स और आपूर्ति श्रृंखला: दूरी या लागत को कम करने के लिए वितरण मार्गों को अनुकूलित करना।
सोशल नेटवर्क: दो लोगों के बीच कनेक्शन की सबसे छोटी श्रृंखला खोजना (डिग्री ऑफ सेपरेशन)।

अक्सर पूछे जाने वाले प्रश्न (FAQs)

डिक्सट्रा एल्गोरिथम क्या है?

डिक्सट्रा एल्गोरिथम 1956 में एड्सगर डब्लू. डिक्सट्रा द्वारा आविष्कार किया गया एक शॉर्टेस्ट पाथ एल्गोरिथम है। यह गैर-ऋणात्मक एज भार वाले भारित ग्राफ में एक एकल स्रोत वर्टेक्स से अन्य सभी वर्टिसेस तक सबसे छोटा (न्यूनतम भार वाला) रास्ता ढूंढता है। यह बार-बार सबसे छोटी ज्ञात अस्थायी दूरी वाले नोड का चयन करके काम करता है।

डिक्सट्रा एल्गोरिथम की क्या सीमाएं हैं?

डिक्सट्रा एल्गोरिथम ऋणात्मक (negative) एज भार वाले ग्राफ में सही ढंग से काम नहीं करता है — यह गलत परिणाम दे सकता है। यदि आपके ग्राफ में ऋणात्मक भार हैं, तो इसके बजाय बेलमैन-फोर्ड एल्गोरिथम का उपयोग करें। डिक्सट्रा का एल्गोरिथम केवल गैर-ऋणात्मक (≥ 0) भारों पर काम करता है।

डिक्सट्रा एल्गोरिथम की समय जटिलता क्या है?

एक सरल सरणी-आधारित कार्यान्वयन O(V²) में चलता है जहाँ V वर्टिसेस की संख्या है। बाइनरी मिन-हीप (प्राथमिकता कतार) का उपयोग करने से यह O((V + E) log V) हो जाता है। फिबोनाची हीप के साथ सैद्धांतिक सर्वोत्तम परिणाम O(E + V log V) है। छोटे ग्राफ (≤15 नोड) के लिए O(V²) दृष्टिकोण बिल्कुल तेज़ है।

मैं कैलकुलेटर के लिए ग्राफ कैसे दर्ज करूँ?

एज लिस्ट टैब का उपयोग करें और From To Weight के प्रारूप में प्रति पंक्ति एक एज दर्ज करें। उदाहरण के लिए, A B 5 भार 5 के साथ A और B के बीच एक एज बनाता है। नोड नाम कोई भी अक्षर या संख्या हो सकते हैं। वैकल्पिक रूप से, ग्रिड इनपुट के लिए आसन्नता आव्यूह टैब का उपयोग करें।

निर्देशित (directed) और अदिशित (undirected) ग्राफ में क्या अंतर है?

एक निर्देशित ग्राफ में, A से B तक की एज केवल A से B तक जाने की अनुमति देती है। अदिशित ग्राफ में, प्रत्येक एज दोनों तरफ काम करती है — A-B का मतलब A→B और B→A दोनों है। डिक्सट्रा का एल्गोरिथम दोनों पर काम करता है, लेकिन सबसे छोटा रास्ता काफी भिन्न हो सकता है।

क्या डिक्सट्रा एल्गोरिथम डिस्कनेक्टेड ग्राफ को संभाल सकता है?

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

संबंधित कैलकुलेटर (Related Calculators)