Dijkstra’s algorithm in Hindi – DAA

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

Dijkstra’s algorithm in Hindi

Dijkstra’s algorithm एक directed weighted ग्राफ पर single-source shortest paths की समस्या को solve करता है.
G = (V,E) जहाँ सभी edges जो है वे non-negative होती हैं.

यह algorithm भी prim’s algorithm की तरह ही समान होती है. prim’s की तरह इसमें भी हम दिए गये source के साथ SPT (shortest path tree) जनरेट करते हैं. इस अल्गोरिथ्म को 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 {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

इस algorithm की complexity पूरी तरह से Extract –min() function की implementation पर निर्भर करता है. यदि extract-min function को linear search का प्रयोग करके implement किया जाता है तो इस अल्गोरिथ्म की complexity – O(V2 + E) होगी. यदि हम min heap का प्रयोग करेंगे तो इसकी complexity और कम हो जाएगी.

Disadvantage of Dijkstra’s algorithm in Hindi

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

  1. यह एक blind search करता है, इसलिए processing में बहुत सारा time बर्बाद हो जाता है.
  2. यह negative edges को handle नही कर सकता है.
  3. यह acyclic graph की ओर जाता है और ज्यादातर सही 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 में किया जाता है.

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

Leave a Comment