Dijkstra’s Shortest Path Algorithm in Hindi


Graphs एक महत्वपूर्ण data structure है, और कई समस्याओं का समाधान पाने के लिए हमें graph में shortest path खोजना होता है। Dijkstra’s Algorithm एक ऐसा algorithm है जो किसी source node से अन्य सभी nodes तक का सबसे कम weight वाला path ढूंढता है। यह weighted graphs पर काम करता है जहां सभी edge weights non-negative होते हैं।

 

आइए इस algorithm को detail में समझते हैं और इसे एक उदाहरण के साथ illustrate करते हैं।

 

Dijkstra’s Algorithm क्या है?

Dijkstra’s Algorithm एक greedy algorithm है जो किसी एक vertex से बाकी सभी vertices तक का shortest path find करता है। यह हर बार सबसे छोटा possible weight वाले edge को चुनकर graph को traverse करता है।

 

Dijkstra’s Algorithm की Process:

  1. Initialization: सभी nodes की distance को infinity (∞) set करें, except source node जिसकी distance 0 होगी।

  2. Mark Visited: Source node को visit करें और उसके सभी neighbors की distances update करें।

  3. Choose Minimum Distance: हर बार unvisited nodes में से वह node चुनें जिसकी current distance सबसे कम है।

  4. Distance Update: Selected node के सभी unvisited neighbors के लिए, distance को update करें अगर current path से travel करने पर shorter path मिलता है।

  5. Repeat: यह process तब तक repeat करें जब तक सभी nodes visit न हो जाएं या desired node तक shortest path न मिल जाए।

 

Dijkstra’s Algorithm का Example:

मान लीजिए हमारे पास एक weighted graph है:

 

       10

   A ------- B

   |            |

   5          1

   |            |

   C ------- D

       2

 

Steps:

  1. Start from A (source) – Set distance of A to 0, and all others to ∞.

  2. Visit A: Update neighbors – B’s distance = 10, C’s distance = 5.

  3. Visit C: Update neighbors – D’s distance = 7 (5+2).

  4. Visit D: Update neighbors – B’s distance becomes 8 (7+1).

  5. Visit B: No more updates.

 

Final shortest distances from A:

  1. A to B: 8

  2. A to C: 5

  3. A to D: 7

 

Dijkstra’s Algorithm के Advantages:

  1. Efficient for Dense Graphs: Dijkstra’s algorithm dense graphs में अच्छी तरह से काम करता है।

  2. Guaranteed Shortest Path: यह हमेशा source node से सभी nodes के लिए shortest path provide करता है।

  3. Non-negative Weights: यह non-negative weights वाले graphs में बेहतर तरीके से काम करता है।

 

Dijkstra’s Algorithm के Disadvantages:

  1. Negative Weights Support नहीं करता: अगर graph में negative weight edges हों, तो यह algorithm fail हो जाता है। इसके लिए Bellman-Ford algorithm का उपयोग करना होगा।

  2. Complexity: Sparse graphs में समय की complexity O(V^2) हो सकती है, जहां V vertices की संख्या है। इसे priority queue के साथ O(E + V log V) तक improve किया जा सकता है।

 

Conclusion

Dijkstra’s Shortest Path Algorithm एक बहुत ही useful technique है जब हमें किसी weighted graph में shortest path find करना हो। यह बहुत efficient है और non-negative weights वाले graphs के लिए ideal है। Dijkstra’s algorithm dense graphs में बेहतर काम करता है और guaranteed shortest path provide करता है। Negative weights वाले graphs के लिए Bellman-Ford जैसी algorithms का उपयोग करना चाहिए।

Related Post