Single Source Shortest Path Algorithm in Hindi | सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम क्या है?

सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम क्या है? (Single Source Shortest Path Algorithm in Hindi)

सिंगल सोर्स शॉर्टेस्ट पाथ (Single Source Shortest Path) समस्या का उद्देश्य किसी ग्राफ में एक स्रोत वर्टेक्स (Source Vertex) से सभी अन्य वर्टिस तक की न्यूनतम दूरी (Shortest Distance) खोजना है। इस समस्या को हल करने के लिए कई एल्गोरिदम मौजूद हैं, जिनमें सबसे प्रमुख हैं:

डिज्कस्ट्रा एल्गोरिदम (Dijkstra’s Algorithm)
बेलमैन-फोर्ड एल्गोरिदम (Bellman-Ford Algorithm)

डिज्कस्ट्रा एल्गोरिदम (Dijkstra’s Algorithm)

डिज्कस्ट्रा एल्गोरिदम का उपयोग एक गैर-ऋणात्मक भारित (Non-Negative Weighted) ग्राफ में सबसे छोटे मार्ग (Shortest Path) को खोजने के लिए किया जाता है। यह ग्रीडी (Greedy) एल्गोरिदम पर आधारित है।

डिज्कस्ट्रा एल्गोरिदम की प्रक्रिया (Process of Dijkstra’s Algorithm)

1. सभी वर्टिस की दूरी को अनंत (∞) और स्रोत वर्टेक्स की दूरी को 0 से प्रारंभ करें।
2. एक प्राथमिकता क्यू (Priority Queue) का उपयोग करें और स्रोत वर्टेक्स को उसमें जोड़ें।
3. प्रत्येक वर्टेक्स के लिए:
   a. निकटतम वर्टेक्स निकालें और उसके पड़ोसी वर्टिस की दूरी अपडेट करें।
   b. यदि कोई नया शॉर्टेस्ट पाथ मिलता है, तो उसे अपडेट करें।
4. जब तक सभी वर्टिस प्रोसेस न हो जाएं, तब तक दोहराएँ।

डिज्कस्ट्रा एल्गोरिदम का उदाहरण (Example of Dijkstra’s Algorithm)

माना कि हमारे पास निम्नलिखित वेटेड ग्राफ है:

स्रोत (Source)	गंतव्य (Destination)	वजन (Weight)
A	B	4
A	C	2
B	C	5
B	D	10
C	D	3

यदि स्रोत वर्टेक्स A है, तो प्रत्येक वर्टेक्स तक की न्यूनतम दूरी:

वर्टेक्स	न्यूनतम दूरी (Shortest Distance)
A	0
B	4
C	2
D	5

बेलमैन-फोर्ड एल्गोरिदम (Bellman-Ford Algorithm)

बेलमैन-फोर्ड एल्गोरिदम का उपयोग ऋणात्मक भारित (Negative Weighted) ग्राफ में सबसे छोटे मार्ग (Shortest Path) को खोजने के लिए किया जाता है। यह डायनामिक प्रोग्रामिंग (Dynamic Programming) तकनीक पर आधारित है।

बेलमैन-फोर्ड एल्गोरिदम की प्रक्रिया (Process of Bellman-Ford Algorithm)

1. सभी वर्टिस की दूरी को अनंत (∞) और स्रोत वर्टेक्स की दूरी को 0 से प्रारंभ करें।
2. प्रत्येक एज (Edge) को V-1 बार रिलैक्स (Relax) करें:
   a. यदि (Distance[u] + Weight of Edge < Distance[v]), तो Distance[v] को अपडेट करें।
3. यदि किसी एज को V-1 बार रिलैक्स करने के बाद भी दूरी कम होती है, तो ग्राफ में एक नेगेटिव साइकिल (Negative Cycle) मौजूद है।

बेलमैन-फोर्ड एल्गोरिदम का उदाहरण (Example of Bellman-Ford Algorithm)

माना कि हमारे पास एक ग्राफ है:

स्रोत (Source)	गंतव्य (Destination)	वजन (Weight)
A	B	4
A	C	2
C	B	-1
B	D	3
C	D	2

यदि स्रोत वर्टेक्स A है, तो बेलमैन-फोर्ड एल्गोरिदम के अनुसार न्यूनतम दूरी:

वर्टेक्स	न्यूनतम दूरी (Shortest Distance)
A	0
B	1
C	2
D	4

सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम की तुलना (Comparison of Algorithms)

एल्गोरिदम	समय जटिलता	ऋणात्मक भार	उपयोगिता
Dijkstra	O(V log V + E)	नहीं	फास्ट और इफेक्टिव
Bellman-Ford	O(VE)	हाँ	नेगेटिव वेट वाले ग्राफ के लिए

सिंगल सोर्स शॉर्टेस्ट पाथ के अनुप्रयोग (Applications of Single Source Shortest Path)

नेटवर्क रूटिंग (Network Routing)
मैपिंग और जीपीएस सिस्टम (Mapping & GPS Systems)
रोबोटिक्स और AI में पथ खोज (Pathfinding in AI and Robotics)
फ्लाइट शेड्यूलिंग (Flight Scheduling)

निष्कर्ष

सिंगल सोर्स शॉर्टेस्ट पाथ समस्या को हल करने के लिए डिज्कस्ट्रा और बेलमैन-फोर्ड एल्गोरिदम का उपयोग किया जाता है। डिज्कस्ट्रा एल्गोरिदम गैर-ऋणात्मक ग्राफ के लिए उपयुक्त है, जबकि बेलमैन-फोर्ड एल्गोरिदम ऋणात्मक भार वाले ग्राफ में भी काम करता है।

NP-Completeness in Hindi | एनपी-कम्प्लीटनेस क्या है?

NP-Completeness क्या है? (NP-Completeness in Hindi) NP-Completeness कम्प्य�...

2-3 Tree in Hindi | 2-3 ट्री क्या है?

2-3 ट्री क्या है? (2-3 Tree in Hindi) 2-3 ट्री (2-3 Tree) एक से...

Height Balanced Tree in Hindi | हाइट बैलेंस्ड ट्री क्या है?

हाइट बैलेंस्ड ट्री क्या है? (Height Balanced Tree in Hindi) ह...

Parallel Algorithm in Hindi | समानांतर एल्गोरिदम क्या है?

समानांतर एल्गोरिदम क्या है? (Parallel Algorithm in Hindi) स...

Lower Bound Theory in Hindi | लोअर बाउंड थ्योरी क्या है?

लोअर बाउंड थ्योरी क्या है? (Lower Bound Theory in Hindi) लो�...

Single Source Shortest Path Algorithm in Hindi | सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम क्या है?