डिजक्स्ट्रा का अल्गोरिद्म
डिजक्स्ट्रा का एल्गोरिथ्म किसी नक्शे के दो स्थानों के बीच सबसे छोटा रास्ता ढूंढने के लिए एक एल्गोरिथ्म है।[2] यह एल्गोरिथ्म कंप्यूटर साइंटिस्ट एस्गर डब्ल्यू॰ डिजक्स्ट्रा के द्वारा 1956 में प्रकाशित की गई थी।[3] एल्गोरिथ्म कई प्रकार में आती है एक प्रकार के अंदर अगर हम स्त्रोत को फिक्स कर दें तो यह हमें स्त्रोत से लेकर सभी स्थानों के बीच में सबसे छोटा रास्ता ढूंढने में मदद करता है। इस एल्गोरिथ्म को संशोधित करके हम एक। स्थान से दूसरे स्थान के बीच में भी छोटा रास्ता ढूंढ सकते हैं। डिजक्स्ट्रा एल्गोरिथ्म को बहुत जगह में यूज किया जाता है जैसे कि एक शहर से दूसरे शहर के बीच में छोटा रास्ता ढूंढने में। इंटरनेट में रूटिंग प्रोटोकोल में छोटा रास्ता ढूंढने में भी डिजक्स्ट्रा का उपयोग किया जाता है।[4]
| Class | Search algorithm Greedy algorithm Dynamic programming[1] |
|---|---|
| Data structure | Graph इसका उपयोग। 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 2223 return dist[], prev[]
अगर हम सबसे छोटी दूरी स्त्रोत से लक्ष्य तक जानना चाहते हैं तो इस शुरु कोड को हम ऐसे अपडेट कर सकते हैं।
1 S ← empty sequence2 u ← target3 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]