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

right|thumb|300px|a और b के मध्य सबसे छोटा पथ प्राप्त करने के लिये डिजक्स्ट्रा की कलनविधि। डिजक्स्ट्रा का एल्गोरिथ्म (Dijkstra's algorithm) किसी नक्शे के दो स्थानों के बीच सबसे छोटा रास्ता ढूंढने के लिए एक एल्गोरिथ्म है।Introduction to algorithms https://archive.org/details/introductiontoal00corm_805 Cormen Thomas H Leiserson Charles E. Rivest Ronald L. Stein Clifford 2009 MIT Press 978-0-262-03384-8 3rd ed. Cambridge, Massachusetts 658-662 अंग्रेज़ी यह एल्गोरिथ्म कंप्यूटर साइंटिस्ट एस्गर डब्ल्यू॰ डिजक्स्ट्रा के द्वारा 1956 में प्रकाशित की गई थी।https://amturing.acm.org/award_winners/dijkstra_1053701.cfm Edsger W. Dijkstra - A.M. Turing Award Laureate amturing.acm.org 2020-08-21 एल्गोरिथ्म कई प्रकार में आती है एक प्रकार के अंदर अगर हम स्त्रोत को फिक्स कर दें तो यह हमें स्त्रोत से लेकर सभी स्थानों के बीच में सबसे छोटा रास्ता ढूंढने में मदद करता है। इस एल्गोरिथ्म को संशोधित करके हम एक। स्थान से दूसरे स्थान के बीच में भी छोटा रास्ता ढूंढ सकते हैं। डिजक्स्ट्रा एल्गोरिथ्म को बहुत जगह में यूज किया जाता है जैसे कि एक शहर से दूसरे शहर के बीच में छोटा रास्ता ढूंढने में। इंटरनेट में रूटिंग प्रोटोकोल में छोटा रास्ता ढूंढने में भी डिजक्स्ट्रा का उपयोग किया जाता है।Cianfrani Antonio Eramo Vincenzo Listanti Marco Marazza Marco Vittorini Enrico 2010-03 An Energy Saving Routing Algorithm for a Green OSPF Protocol https://ieeexplore.ieee.org/abstract/document/5466646/ 2010 INFOCOM IEEE Conference on Computer Communications Workshops 1–5 10.1109/INFCOMW.2010.5466646 यह एल्गोरिथ्म मूल रूप से विभिन्न रचनाओं का उपयोग करता है। डिजक्स्ट्रा की मूल एल्गोरिथ्म दिये गये दो नोड के मध्य लघुतम पथ ज्ञात करने के लिए किया जाता है। स्यूडोकोडDijkstra's algorithm 2020-08-13 https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=972687034 Wikipedia en 2020-08-21 हम सबसे पहले एक सेट 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 u ← target 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] सन्दर्भ