भारित ग्राफ में सबसे छोटा पथ: डीजकस्ट्रा और बेलमैन-फोर्ड एल्गोरिद्म

ग्राफ सिद्धांत में सबसे महत्वपूर्ण समस्याओं में से एक है Shortest Path Problem — यानी किसी स्रोत नोड (Source Node) से अन्य सभी नोड्स तक न्यूनतम दूरी खोजना। इस समस्या को हल करने के लिए दो प्रमुख एल्गोरिद्म का उपयोग किया जाता है — डीजकस्ट्रा एल्गोरिद्म (Dijkstra's Algorithm) और बेलमैन-फोर्ड एल्गोरिद्म (Bellman-Ford Algorithm)। दोनों का प्रयोग नेटवर्किंग, ट्रैफिक सिस्टम, और डेटा ट्रांसमिशन में किया जाता है।

1️⃣ भारित ग्राफ का परिचय (Introduction to Weighted Graph)

Weighted Graph वह ग्राफ होता है जिसमें हर edge के साथ एक मान (Weight) जुड़ा होता है। यह मान दूरी, समय, लागत या अन्य मापदंड को दर्शाता है। उदाहरण के लिए, यदि किसी शहर A से शहर B तक 5 किलोमीटर की दूरी है, तो edge (A,B) का weight = 5 होगा।

2️⃣ Shortest Path Problem क्या है?

इस समस्या का उद्देश्य है — दिए गए स्रोत vertex से सभी अन्य vertices तक सबसे कम वज़न वाला मार्ग खोजना।

इसका उपयोग कई जगहों पर होता है:

• Google Maps में सबसे छोटा रास्ता बताने के लिए
• नेटवर्क पैकेट रूटिंग (Routing Algorithms) में
• Airline Flight Scheduling में

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

डीजकस्ट्रा एल्गोरिद्म एक ग्रीडी एल्गोरिद्म है जो पॉजिटिव वेट वाले ग्राफ में सबसे छोटा पथ निकालने के लिए प्रयोग किया जाता है।

एल्गोरिद्म के चरण (Steps):

1. सभी नोड्स की दूरी को अनंत (∞) से आरंभ करें। स्रोत नोड की दूरी 0 रखें।
2. सबसे छोटे distance वाले vertex का चयन करें।
3. उस vertex के सभी पड़ोसी vertices की दूरी अपडेट करें यदि नया पथ छोटा है।
4. चयनित vertex को “visited” मार्क करें।
5. यह प्रक्रिया तब तक दोहराएँ जब तक सभी vertices का दौरा न हो जाए।

उदाहरण:

Vertices: A, B, C, D, E
Edges:
A-B(4), A-C(2), B-C(5), B-D(10), C-D(3), D-E(4)

Source = A

• Step 1: Distance(A)=0, अन्य सभी = ∞
• Step 2: A से सबसे छोटा रास्ता → C (2)
• Step 3: C → D (2+3=5), B (4)
• Step 4: D → E (5+4=9)

Final Shortest Paths:

A → C = 2
A → B = 4
A → D = 5
A → E = 9

जटिलता (Complexity):

O(V²) या Priority Queue (Heap) के प्रयोग से O(E log V)

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

Bellman-Ford एल्गोरिद्म का प्रयोग तब किया जाता है जब ग्राफ में Negative Weights भी हों। यह Dynamic Programming तकनीक पर आधारित है।

एल्गोरिद्म के चरण:

1. सभी vertices की दूरी ∞ से शुरू करें; source = 0 रखें।
2. हर edge (u, v) के लिए V-1 बार Relax ऑपरेशन करें:
   यदि distance[v] > distance[u] + weight(u, v), तो distance[v] अपडेट करें।
3. अंत में, Negative Weight Cycle की जांच करें। यदि किसी edge को अभी भी Relax किया जा सकता है, तो cycle मौजूद है।

उदाहरण:

Vertices: A, B, C
Edges:
A-B(1), B-C(-1), C-A(2)

यह ग्राफ negative edges संभाल सकता है, लेकिन negative cycle नहीं।

जटिलता (Complexity):

O(VE)

5️⃣ Dijkstra vs Bellman-Ford तुलना

विशेषता	डीजकस्ट्रा	बेलमैन-फोर्ड
वेट का प्रकार	Positive	Positive + Negative
Approach	Greedy	Dynamic Programming
समय जटिलता	O(V²) / O(E log V)	O(VE)
Negative Cycle Detection	No	Yes

6️⃣ अनुप्रयोग (Applications)

• Network Routing Protocols (OSPF, RIP)
• Map Navigation Systems
• AI Pathfinding Algorithms
• Transportation and Logistics Optimization

7️⃣ वास्तविक जीवन उदाहरण

Google Maps जब shortest route निकालता है, तो वह इसी प्रकार के एल्गोरिद्म का उपयोग करता है। यदि सभी मार्गों के वज़न positive हैं तो Dijkstra; यदि कुछ penalty या delay negative हो सकते हैं, तो Bellman-Ford उपयुक्त है।

🔟 निष्कर्ष

Dijkstra’s Algorithm तेज़ और प्रभावी है, लेकिन Bellman-Ford अधिक सामान्य (generalized) है। दोनों ही नेटवर्क और कंप्यूटर विज्ञान के मूलभूत टूल्स हैं। “Dijkstra ensures speed, Bellman-Ford ensures correctness.”