Dijkstra’s Algorithm क्या है?

Hello दोस्तों आज मैं आपको इस आर्टिकल में Dijkstra’s algorithm in Hindi  (दीजकस्ट्रा का एल्गोरिदम क्या है?) के बारें में बताऊंगा और इसके disadvantages के बारें में भी पढेंगे, तो चलिए शुरू करते हैं:-

Dijkstra’s algorithm in Hindi

Dijkstra’s algorithm एक directed weighted graph में single-source shortest path समस्या को हल करता है।
G = (V, E) जहाँ सभी edges non-negative होती हैं।

यह algorithm Prim’s algorithm के समान होती है। Prim’s की तरह इसमें भी हम दिए गए source के साथ SPT (Shortest Path Tree) जनरेट करते हैं। इस algorithm को 1959 में Dutch वैज्ञानिक Edsger Dijkstra ने प्रस्तावित किया था। यह एक greedy algorithm है।

नीचे आपको algorithm दी गई है, जिसमें हमने एक फ़ंक्शन Extract-Min() का प्रयोग किया है, जो सबसे छोटी key के साथ node को extract करता है।

Algorithm: Dijkstra’s-Algorithm (G, w, s) 

for each vertex v ∈ G.V  
   v.d := ∞  
   v.∏ := NIL  
s.d := 0  
S := ∅  
Q := G.V  
while Q ≠ ∅  
   u := Extract-Min (Q)  
   S := S ∪ {u}  
   for each vertex v ∈ G.adj[u]  
      if v.d > u.d + w(u, v)  
         v.d := u.d + w(u, v)  
         v.∏ := u  

Complexity of Dijkstra’s Algorithm

इस algorithm की complexity पूरी तरह से Extract-Min() फ़ंक्शन की implementation पर निर्भर करती है।

यदि हम min-heap (binary heap) का उपयोग करें, तो complexity O((V + E) log V) हो जाएगी।

यदि Extract-Min() फ़ंक्शन को linear search द्वारा implement किया जाए, तो इसकी complexity O(V²) होगी।

Disadvantage of Dijkstra’s algorithm in Hindi

इसकी हानियाँ निम्नलिखित हैं:-

1. यह एक blind search करता है, इसलिए processing time ज्यादा हो सकता है।
2. यह negative weight edges को handle नहीं कर सकता।
3. यह acyclic graphs तक सीमित नहीं है, लेकिन यदि negative weight cycles हों, तो सही shortest path नहीं दे पाता।
4. हमें उन vertices पर नज़र रखनी होती है, जिन्हें एक बार visit कर लिया जाता है।

Applications of Dijkstra’s algorithm in Hindi

इसके अनुप्रयोग निम्नलिखित हैं:-

1. इसका प्रयोग traffic information system में किया जाता है.
2. open-source path first (OSPF) में इसका use होता है.
3. routing management के लिए telephone और cellular networks में इसका use किया जाता है.
4. इसका प्रयोग geographic information system (GIS) जैसे:- google map में किया जाता है.

इसे पढ़ें:-

• Graph क्या है और इसके प्रकार
• Tree क्या है और इसके प्रकार

निवेदन:- अगर आपके लिए यह पोस्ट थोड़ी सी भी मददगार रही हो तो इसे अपने friends के साथ अवश्य share कीजिये और आपके जो भी questions हैं आप उन्हें नीचे comment करके बता सकते हैं.