Shortest Path in Weighted Graph in Hindi – Definition, Algorithms, and Examples


Shortest Path in Weighted Graph क्या है?

Graph Theory में Shortest Path वह Path होता है, जो Graph में एक Vertex से दूसरे Vertex तक पहुंचने के लिए कम से कम Weight (Cost, Distance, या Time) लेता है। Weighted Graph में प्रत्येक Edge का एक Weight (मूल्य) होता है, जो Cost या Distance को दर्शाता है।

Shortest Path की परिभाषा (Definition of Shortest Path)

Shortest Path दो Vertices के बीच का वह Path है, जिसमें Edges का कुल Weight सबसे कम होता है। इसे विभिन्न प्रकार के Weighted Graphs में खोजने के लिए कई Algorithms का उपयोग किया जाता है।

Applications of Shortest Path

Shortest Path का उपयोग कई वास्तविक जीवन की समस्याओं को हल करने में किया जाता है:

  1. Google Maps में Shortest Route खोजना
  2. Network Routing
  3. Project Scheduling
  4. Flight Reservation Systems
  5. Transportation Networks

Algorithms to Find Shortest Path (Shortest Path खोजने के लिए एल्गोरिदम)

Shortest Path को खोजने के लिए विभिन्न Algorithms का उपयोग किया जाता है। निम्नलिखित मुख्य Algorithms हैं:

1. Dijkstra's Algorithm

Dijkstra's Algorithm एक Greedy Algorithm है, जो Non-Negative Weights वाले Graphs में Shortest Path खोजने के लिए उपयोग किया जाता है।

Steps of Dijkstra's Algorithm:

  1. Initial Vertex से सभी अन्य Vertices की Distance को Infinity के रूप में Set करें। Initial Vertex की Distance को 0 करें।
  2. हर Iteration में, उस Vertex को Select करें जिसकी Distance सबसे कम हो।
  3. उसके Neighbors की Distance को Update करें।
  4. प्रक्रिया तब तक दोहराएं जब तक सभी Vertices की Distance मिल न जाए।

Example of Dijkstra's Algorithm:

मान लीजिए कि एक Weighted Graph में Vertices A, B, C, D, और E हैं। A से E तक का Shortest Path Dijkstra's Algorithm का उपयोग करके खोजा जा सकता है।

2. Bellman-Ford Algorithm

Bellman-Ford Algorithm Negative Weights वाले Graphs में भी Shortest Path खोजने में सक्षम है। हालांकि, यह Dijkstra's Algorithm की तुलना में धीमा होता है।

Steps of Bellman-Ford Algorithm:

  1. सभी Edges को |V|-1 बार Relax करें (जहाँ V = Vertices की संख्या)।
  2. Check करें कि कहीं Negative Cycle तो नहीं है।
  3. यदि Negative Cycle नहीं है, तो Shortest Path Return करें।

Example of Bellman-Ford Algorithm:

यह Algorithm Financial Networks और Currency Arbitrage में उपयोगी होती है, जहाँ Negative Weights की आवश्यकता होती है।

Comparison of Dijkstra's and Bellman-Ford Algorithms

Algorithm Time Complexity Handles Negative Weights
Dijkstra's Algorithm O(V + E log V) नहीं
Bellman-Ford Algorithm O(VE) हाँ

Applications of Dijkstra's and Bellman-Ford Algorithms

इन Algorithms का उपयोग विभिन्न क्षेत्रों में किया जाता है:

  1. Dijkstra's Algorithm: Navigation Systems, Network Routing
  2. Bellman-Ford Algorithm: Financial Systems, Currency Arbitrage, Network Analysis

Conclusion

Shortest Path Algorithms Weighted Graphs में एक Vertex से दूसरे Vertex तक कम से कम Weight के साथ Path खोजने में सहायक होते हैं। Dijkstra's Algorithm Non-Negative Weights के लिए सबसे उपयुक्त है, जबकि Bellman-Ford Algorithm Negative Weights के साथ उपयोग किया जाता है। इन Algorithms का उपयोग कई क्षेत्रों में किया जाता है, जिससे वे Graph Theory में अत्यधिक महत्वपूर्ण बन जाते हैं।

Related Post