डिजक्स्ट्रा का अल्गोरिद्म

दो बिंदुओं के बीच सबसे सूक्ष्म पथ ढूंढने वाला एल्गोरिथम

डिजक्स्ट्रा का एल्गोरिथ्म किसी नक्शे के दो स्थानों के बीच सबसे छोटा रास्ता ढूंढने के लिए एक एल्गोरिथ्म है।[2] यह एल्गोरिथ्म कंप्यूटर साइंटिस्ट एस्गर डब्ल्यू॰ डिजक्स्ट्रा के द्वारा 1956 में प्रकाशित की गई थी।[3] एल्गोरिथ्म कई प्रकार में आती है एक प्रकार के अंदर अगर हम स्त्रोत को फिक्स कर दें तो यह हमें स्त्रोत से लेकर सभी स्थानों के बीच में सबसे छोटा रास्ता ढूंढने में मदद करता है। इस एल्गोरिथ्म को संशोधित करके हम एक। स्थान से दूसरे स्थान के बीच में भी छोटा रास्ता ढूंढ सकते हैं। डिजक्स्ट्रा एल्गोरिथ्म को बहुत जगह में यूज किया जाता है जैसे कि एक शहर से दूसरे शहर के बीच में छोटा रास्ता ढूंढने में। इंटरनेट में रूटिंग प्रोटोकोल में छोटा रास्ता ढूंढने में भी डिजक्स्ट्रा का उपयोग किया जाता है।[4]

डिजक्स्ट्रा का एल्गोरिथ्म
ClassSearch algorithm
Greedy algorithm
Dynamic programming[1]
Data structureGraph
इसका उपयोग। Priority queue/Heap ताकि इसका समय सुधारा जा सके।
Average performance
Worst-case space complexity

यह एल्गोरिथ्म मूल रूप से विभिन्न रचनाओं का उपयोग करता है। डिजक्स्ट्रा की मूल एल्गोरिथ्म दिये गये दो नोड के मध्य लघुतम पथ ज्ञात करने के लिए किया जाता है।

स्यूडोकोड[5] संपादित करें

हम सबसे पहले एक सेट create vertex set Q बनाएंगे जिसके अंदर हमारे सारे वर्टेक्स होंगे। उसके बाद हम अपना डिस्टेंस मैट्रिक्स dist[v] लेंगे जिसके अंदर हम सबसे छोटी दूरी को रखेंगे। डिस्टेंस मैट्रिक्स के अंदर हमने अभी सभी की वैल्यू को इंफिनिटी रख दिया है। यह पंक्तिमें u ← vertex in Q with min dist[u] सबसे छोटी दूरी निकाल कर देगा। हम स्त्रोत से दूरी को चेक करेंगे अगर यह छोटी है तो हम अपने डिस्टेंस मैट्रिक्स के अंदर इसको अपडेट alt ← dist[u] + length(u, v) कर देंगे। यह प्रक्रिया तब तक चलती रहेगी जब तक हीप खाली ना हो जाए।

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             
 6          dist[v] ← INFINITY                  
 7          prev[v] ← UNDEFINED                 
 8          add v to Q                      
10      dist[source] ← 0                        
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    
14                                              
15          remove u from Q 
16          
17          for each neighbor v of u:           
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               
20                  dist[v] ← alt 
21                  prev[v] ← u 
22
23      return dist[], prev[]

अगर हम सबसे छोटी दूरी स्त्रोत से लक्ष्य तक जानना चाहते हैं तो इस शुरु कोड को हम ऐसे अपडेट कर सकते हैं।

1  S ← empty sequence
2  utarget
3  if prev[u] is defined or u = source:          
4      while u is defined:                      
5          insert u at the beginning of S        
6          u ← prev[u]                           

सन्दर्भ संपादित करें

  1. Controversial,see Moshe Sniedovich (2006). "Dijkstra's algorithm revisited: the dynamic programming connexion". Control and Cybernetics. 35: 599–620. and below part.
  2. Cormen, Thomas H; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to algorithms (अंग्रेज़ी में) (3rd ed. संस्करण). Cambridge, Massachusetts: MIT Press. पपृ॰ 658-662. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.सीएस1 रखरखाव: फालतू पाठ (link)
  3. "Edsger W. Dijkstra - A.M. Turing Award Laureate". amturing.acm.org. अभिगमन तिथि 2020-08-21.
  4. Cianfrani, Antonio; Eramo, Vincenzo; Listanti, Marco; Marazza, Marco; Vittorini, Enrico (2010-03). "An Energy Saving Routing Algorithm for a Green OSPF Protocol". 2010 INFOCOM IEEE Conference on Computer Communications Workshops: 1–5. डीओआइ:10.1109/INFCOMW.2010.5466646. |date= में तिथि प्राचल का मान जाँचें (मदद)
  5. "Dijkstra's algorithm", Wikipedia (अंग्रेज़ी में), 2020-08-13, अभिगमन तिथि 2020-08-21