Dijkstra’s Shortest Path Algorithm
Dijkstra’s Algorithm एक graph algorithm है, जो किसी weighted graph में एक source vertex से सभी other vertices तक का shortest path या minimum distance path खोजने के लिए use किया जाता है।
Key Points
- Positive weights वाली edges के लिए use होता है।
- हर step में current minimum distance vertex को select करता है।
- Neighbor vertices की distances update करता है।
- Visited vertices की distance final होती है।
- Single-source shortest path problem का solution देता है।
Algorithm Steps
1. Initialization
- Source vertex का distance = 0
- सभी other vertices का distance = ∞ (infinity)
- Visited set को empty रखें
2. Select Minimum Distance Vertex
- Unvisited vertices में से distance सबसे कम वाला vertex select करें
- इसे current vertex मानें
3. Update Neighbors
- Current vertex से directly connected neighbors की distance check करें
Formula :
new_distance = distance[current_vertex] + weight(current_vertex, neighbor)
if new_distance < distance[neighbor] : distance[neighbor] = new_distance
4. Mark Current Vertex as Visited
- Visited vertex को फिर से select नहीं किया जाएगा
- इसका distance अब final और minimum है|
5. Repeat Steps
- Step 2–4 repeat करें जब तक सभी vertices visited न हो जाएँ
6. Output
- Distance array में source से सभी vertices तक का shortest path distance मिलेगा
Pseudo Code
function Dijkstra(Graph, source):
dist[source] = 0 // Source vertex ka distance hamisha 0 hota hai.
for each vertex v in Graph:
if v ≠ source:
dist[v] = ∞ // Baaki saare vertices ka initial distance infinite mana jata hai.
visited = empty set
while all vertices are not visited:
u = vertex with minimum dist[u] not in visited
visited.add(u)
for each neighbor v of u:
if v not in visited:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
return dist // Sabhi vertices tak ke shortest distances return karta hai.
Example (उदाहरण)
Step by Step Calculation from A :
- Initial Distances :
- A = 0, B = ∞, C = ∞, D = ∞, E = ∞
- Pick A (distance 0) → Update B = 4, C = 2
- Pick C (distance 2) → Update D = 5 (C→D = 3)
- Pick B (distance 4) → D already 5 → no change
- Pick D (distance 5) → Update E = 6 (D→E = 1)
- Pick E (distance 6) → A already 0 → no change
Result (Shortest distances from A) :
A = 0, B = 4, C = 2, D = 5, E = 6
Applications of Dijkstra’s Shortest Path Algorithm (उपयोग)
1. GPS Navigation Systems
- Google Maps, Apple Maps, GPS devices में shortest route निकालने के लिए।
- Example : घर से College तक minimum time या minimum distance वाला रास्ता दिखाना।
2. Network Routing
- Internet routers data packets को कम delay वाले path से भेजते हैं।
- OSPF (Open Shortest Path First) routing protocol में Dijkstra’s Algorithm का उपयोग होता है।
3. Telecommunications
- Mobile/Telephone networks में signal routing के लिए।
- Minimum cost communication path ढूँढने में मदद करता है।
4. Transportation & Logistics
- Roads, Railways, Airlines में shortest route planning के लिए।
- Delivery companies (जैसे courier, e-commerce) minimum time में goods deliver करने के लिए।
5. Robotics & AI Pathfinding
- Robots intelligent navigation के लिए shortest safe path चुनते हैं।
Games में characters smart तरीके से move करते हैं (maze solving, game maps)।
6. Electrical Grid Optimization
- Power stations से अलग-अलग areas में efficient power distribution।
- Minimum cost wiring या network design करने में उपयोगी।
7. Urban Planning
- New roads, transport routes और public utility paths design करने में।
- Traffic optimization systems में shortest congestion-free routes decide करने के लिए।
8. Flight Route Optimization
Airlines fuel-efficient या shortest flight paths चुनने के लिए।
9. Computer Games
Strategy, Racing, Simulation games में smart pathfinding behavior बनाने में।
10. Data Center Load Balancing
Data packets के लिए least delay वाले path choose करके network performance बढ़ाने में उपयोग होता है।
Advantages of Dijkstra’s Algorithm (लाभ)
1. Fast and Efficient
- Weighted graphs में shortest path निकालने के लिए यह बहुत तेज़ और efficient algorithm है।
- Greedy approach होने की वजह से computation कम होता है।
2. Finds Optimal Shortest Path
Positive weight graphs में हमेशा guaranteed optimal shortest path देता है।
3. Works for Large Graphs
Priority Queue / Min-Heap उपयोग करने पर बड़े graphs में भी बहुत अच्छा perform करता है।
4. Single Source to All Vertices
Dijkstra Algorithm एक बार run करने पर source vertex से सभी अन्य vertices तक के shortest distances प्राप्त हो जाते हैं।
5. Real-World Applications में Useful
GPS Navigation, Network Routing, Robotics, Games, Airline Routes जैसे कई real-world systems में use होता है।
6. Easy to Understand and Implement
- Algorithm की logic simple है:
- minimum distance vertex select करना
- उसके neighbors update करना
- इसलिए students और developers दोनों के लिए आसान है।
7. No Need to Explore All Paths
- Greedy method की वजह से unnecessary long paths को ignore कर देता है। इससे time complexity कम रहती है।
Disadvantages of Dijkstra’s Algorithm (सीमाएँ)
1. Does not work on negative weight edges
- यदि graph में negative weights हों तो algorithm गलत result दे सकता है।
2. Does not work on negative weight edges
- बहुत बड़े graphs में, खासकर बिना priority queue के, algorithm काफी slow काम करता है।
3. Only Single Source Shortest Path
- यह सिर्फ एक source vertex से ही shortest paths निकालता है।
- Multiple sources के लिए algorithm को कई बार चलाना पड़ता है।
4. Higher Memory Requirement
- Distances, visited set और priority queue store करने में अधिक memory लगती है।
5. Re-running when the graph is updated
- Graph में कोई नया edge add/remove हो जाए तो algorithm को start से re-run करना पड़ता है।
6. Time Complexity Increases in Dense Graphs
- यदि graph में बहुत ज़्यादा edges हों (dense graph), तो neighbors update करने में time complexity बढ़ती है।
7. Limited Use in Real-Time Applications
- जहाँ real-time updates चाहिए (जैसे heavy traffic changing routes), वहाँ बार-बार recomputation costly हो जाता है।
