डिज्स्कट्रा का एल्गोरिथ्म: C++, Python कोड उदाहरण
सबसे छोटा रास्ता या सबसे छोटी दूरी क्या है?
स्रोत शीर्ष से गंतव्य शीर्ष तक का वह पथ जिसकी लागत न्यूनतम हो, सबसे छोटा पथ या सबसे छोटी दूरी होती है। ग्राफ सिद्धांत में, स्रोत से गंतव्य तक कई मार्ग होना संभव है। इन मार्गों के बीच, यदि कोई ऐसा मार्ग है जिसकी लागत न्यूनतम हो, तो हम उसे सबसे छोटा पथ एल्गोरिथम कह सकते हैं।
यहाँ "लागत" का अर्थ है मार्ग में नोड्स की संख्या या प्रत्येक पथ पर लागतों का योग। एक पथ में एक या कई किनारे हो सकते हैं। दो शीर्षों के बीच के कनेक्शन को "किनारा" कहा जाता है। सबसे छोटे पथ एल्गोरिदम के विभिन्न प्रकार हैं, जैसे कि डिज्कस्ट्रा का एल्गोरिदम, बेलमैन-फ़ोर्ड एल्गोरिदम, आदि।
यहाँ, हम डिज्कस्ट्रा के एल्गोरिथ्म के बारे में चर्चा करते हैं
आइये निम्नलिखित भारित ग्राफ को देखें:
- "भारित" शब्द का अर्थ है एक नोड से दूसरे नोड पर जाने वाली लागत। उदाहरण के लिए, नोड 1 से नोड 2 पर जाने पर लागत या भार 1 होता है।
- नोड 1 से नोड 2 के बीच के पथ को किनारा कहा जाता है।
- "अनिर्देशित" का अर्थ है कि आप एक नोड को दूसरे नोड पर ले जा सकते हैं और पिछले नोड पर वापस ला सकते हैं। इसलिए, यदि हम नोड 1 से नोड 7 तक सभी रूट खोजने का प्रयास करते हैं, तो यह होगा:
मार्ग या पथ | लागत |
---|---|
1-2-6-7 | (1+3+3) = 7 |
1-2-3-7 | (1+9+1) = 11 |
1-3-7 | (7+1) = 8 |
1-4-5-7 | (6+2+5) = 13 |
इन चार मार्गों में से, हम देख सकते हैं कि पहले मार्ग पर हमें 7 का खर्च आएगा। इसलिए, लागत की दृष्टि से यह सबसे छोटा रास्ता है।
डिज्कस्ट्रा का एल्गोरिदम कैसे काम करता है
डिज्कस्ट्रा एल्गोरिदम निर्देशित और अनिर्देशित भारित ग्राफ़ दोनों में सबसे छोटी दूरी का पता लगा सकता है। यह एल्गोरिदम लालची है क्योंकि यह हमेशा मूल से सबसे छोटा या निकटतम नोड चुनता है। "लालची" शब्द का अर्थ है कि परिणामों या परिणामों के एक सेट में से, एल्गोरिदम उनमें से सबसे अच्छा चुनेगा।
यहाँ, हम सभी अन्य मार्गों में से सबसे छोटे पथ को खोजने का प्रयास कर रहे हैं। इसलिए, डिज्कस्ट्रा का एल्गोरिथ्म एक ही गंतव्य नोड से सभी सबसे छोटे पथों को खोजता है। परिणामस्वरूप, यह एक तरह से व्यवहार करता है लालची एल्गोरिथ्म.
नीचे दिए गए “उदाहरण” अनुभाग में, आपको चरण-दर-चरण दृष्टिकोण दिखाई देगा। यह इस प्रकार काम करता है:
चरण 1) प्रारंभिक नोड को 0 लागत के साथ और शेष नोड को अनंत लागत के साथ आरंभ करें।
चरण 2) विज़िट किए गए नोड्स का ट्रैक रखने के लिए एक सरणी या सूची बनाए रखें
चरण 3) नोड लागत को न्यूनतम लागत के साथ अपडेट करें। यह वर्तमान लागत की तुलना पथ लागत से करके किया जा सकता है। (प्रदर्शन उदाहरण अनुभाग में दिखाया गया है)
चरण 4) चरण 3 को तब तक जारी रखें जब तक सभी नोड का दौरा न हो जाए।
इन सभी चरणों को पूरा करने के बाद, हम स्रोत से गंतव्य तक न्यूनतम लागत वाला मार्ग खोज लेंगे।
डिज्कस्ट्रा और बीएफएस, डीएफएस के बीच अंतर
डिज्कस्ट्रा और बीएफएस-डीएफएस के बीच मुख्य अंतर यह है कि डिज्कस्ट्रा सबसे छोटा पथ खोजने वाला एल्गोरिदम है, और बीएफएस, डीएफएस पथ खोजने वाला एल्गोरिदम है। सामान्य मामलों में, बीएफएस और डीएफएस पथ खोजते समय लागत पर विचार नहीं करते हैं। इसलिए, ये एल्गोरिदम सबसे छोटे पथ की गारंटी नहीं दे सकते।
बीएफएस कैसे काम करता है इसका 2डी ग्रिड प्रदर्शन
यह प्रदर्शन दर्शाता है कि BFS केवल पथ ढूँढता है। हालाँकि, यह पथ के भार की परवाह नहीं करता है। BFS (पहले चौड़ाई खोजो) यह मानता है कि एक नोड से दूसरे नोड तक यात्रा करने में केवल 1 का खर्च आएगा।
लेकिन आइये एक उदाहरण ग्राफ देखें:
यहाँ, यह लेवल 2 में एक पथ ढूँढता है। BFS लेवल क्रम में ग्राफ को पार करता है। इसलिए, यह इस तरह से यात्रा करता है:
चरण 1) नोड “1” से शुरू करें और सभी आसन्न नोड्स 2,3,4 पर जाएँ
चरण 2) नोड 2,3,4 को लेवल 1 के रूप में चिह्नित करें और उनके आस-पास के नोड्स पर जाएँ। यह गंतव्य नोड तक पहुँचने तक सभी आस-पास के नोड्स की खोज जारी रखेगा।
डीएफएस के संदर्भ में, यह 1 से 7 तक का मार्ग इस प्रकार तय करेगा:
- 1→2→3→7 (मूल लागत 10, डीएफएस लागत 3)
- 1→2→6→7 (मूल लागत 7, डीएफएस लागत 3)
- 1→3→7 (मूल लागत 8, डीएफएस लागत 2)
- 1→4→5→7 (मूल लागत 13, डीएफएस लागत 3)
जैसा कि हम देखते हैं, DFS अपनी पथ लागत की गणना गहराई की संख्या या किनारों की संख्या के आधार पर करता है।
डीएफएस निम्नलिखित कार्य करता है:
- डीएफएस स्रोत (प्रारंभिक शीर्ष) से गंतव्य तक का रास्ता ढूंढ सकता है।
- यह गारंटी नहीं दे सकता कि स्रोत नोड से गंतव्य तक खोजा गया पथ सबसे छोटा पथ है या नहीं।
हालाँकि, डिज्कस्ट्रा एल्गोरिथ्म के संदर्भ में, यह उनकी लागत के आधार पर किनारों का चयन करेगा। एक लालची एल्गोरिथ्म के रूप में, यह सबसे अच्छा या न्यूनतम लागत वाला रास्ता चुनेगा।
डिज्कस्ट्रा के एल्गोरिथ्म का उदाहरण
डिज्कस्ट्रा का एल्गोरिथ्म पथ की कुल लागत की गणना करने के लिए लागत या भार का उपयोग करता है।
डिज्कस्ट्रा के एल्गोरिदम का लक्ष्य इस कुल लागत या भार को कम करना है। ऊपर दिखाए गए उदाहरण में, हम नोड 1 से नोड 7 तक के सर्वोत्तम पथ ढूंढते हैं, फिर सभी लागतों की गणना करते हैं।
डिज्कस्ट्रा के एल्गोरिथ्म में, यह भार की गणना करके सबसे छोटे रास्ते खोजेगा। यह सभी संभावित रास्तों की खोज नहीं करेगा। आइए हम एक उदाहरण के साथ डिज्कस्ट्रा के एल्गोरिथ्म को प्रदर्शित करें। उदाहरण के लिए, आपको नोड 1 से 7 तक का सबसे छोटा रास्ता खोजने के लिए कहा गया है।
इस प्रक्रिया के लिए नीचे चरण दिए गए हैं:
चरण 1) प्रारंभिक नोड लागत को 0 पर आरंभ करें।
शेष नोड, असाइन करें “इन्फ़”। इसका अर्थ है कि प्रारंभिक शीर्ष (स्रोत) और नोड के बीच कोई पथ मौजूद नहीं है, या पथ पर अभी तक जाया नहीं गया है।
चरण 2) जब आप नोड 1 का चयन करते हैं, तो इसे विज़िट किए गए के रूप में चिह्नित किया जाएगा। फिर नोड 1 के सभी आसन्न पड़ोसियों को अपडेट करें। 2,3,4 नोड 1 के पड़ोसी नोड हैं।
लागत को अद्यतन करते समय, हमें नीचे दी गई प्रक्रिया का पालन करना होगा:
हम उपरोक्त सूत्र का उपयोग करके प्रत्येक नोड की लागत को अपडेट कर सकते हैं। उदाहरण के लिए, हम नोड 1 पर थे, और हमें इसके निकटवर्ती नोड 2,3,4 की लागत को अपडेट करना था।
अपडेट करने के बाद, लागत या वजन इस तरह दिखेगा:
चरण 3) नोड “2” के लिए, पड़ोसी 6 और 3 हैं। हम अनंत (वर्तमान मूल्य) की तुलना करके लागत को “6” पर अपडेट कर रहे हैं। नोड 2 की लागत + 2 से 6 तक पथ लागत। सीधे शब्दों में कहें तो नोड “6” की लागत 1+3 या 4 होगी।
नोड 3, नोड 2 का पड़ोसी है। हालाँकि, हमने पिछले चरण में इसकी लागत की गणना की थी, जो 7 थी। अब, यदि हमारा पथ 1-2-3 है, तो नोड 3 की लागत 10 होगी। पथ 1-2-3 की लागत 10 होगी, जबकि 1 से 3 की लागत 7 होगी।
चरण 4) नोड 3 के लिए, पड़ोसी नोड 7 है। इसलिए, नोड 7 के वर्तमान मूल्य की पथ लागत (7+1) या 8 के साथ तुलना करके, हम नोड 7 की लागत को अपडेट करेंगे। जो 8 है।
तो, हम नोड 1 से नोड 7 तक का रास्ता ढूंढते हैं, और यह 1→ 3→ 7 है। लागत 8 है।
चरण 5) नोड 4 के लिए, हम इसके आस-पास के नोड की लागत को तदनुसार अपडेट करेंगे। इसलिए, नोड “5” की अपडेट की गई लागत 8 होगी। चरण 4,5 के बाद, यह इस तरह दिखेगा:
अब, पथ 1-3-7 की लागत 8 है (पहले)। नोड “7” को विज़िट किया हुआ नहीं माना गया क्योंकि हम नोड “7” से नोड “6” तक पहुँच सकते हैं। पथ “1-2-6” की लागत 4 थी। इसलिए पथ 1-2-6-7 की लागत 7 होगी।
चूँकि 7 < 8, इसीलिए स्रोत शीर्ष "1" से गंतव्य शीर्ष "7" तक का सबसे छोटा रास्ता 1-2-6-7 होगा, और लागत 7 होगी। पहले यह 1-3-7 था, और लागत 8 थी।
तो, अंतिम ग्राफ इस तरह दिखेगा:
काली रेखा से चिह्नित किनारा 1 से 7 तक हमारा सबसे छोटा रास्ता है, और इसकी लागत हमें 7 होगी।
छद्म कोड डिज्कस्ट्रा का एल्गोरिदम
यहां डिज्कस्ट्रा के एल्गोरिथ्म के लिए छद्म कोड दिया गया है
Dijkstra(G, S): for each vertex V in G distance[V] & lt; - Infinity previous[V] & lt; - NULL if V does not equal S, then, (priority queue) Q.push(V) distance[S] = 0 While Q is not empty U & lt; - Extract the MIN from Q For each unvisited adjacent V of U TotalDistance & lt; - distance[U] + edge_cost(U, V) if TotalDistance is less than distance[V], then distance[V] & lt; - TotalDistance previous[V] & lt; - u return distance, previous
C++ कार्यान्वयन डिज्कस्ट्रा एल्गोरिथ्म
डिज्कस्ट्रा के एल्गोरिथ्म को लागू करने के लिए C++, कोड यह है:
#include <bits/stdc++.h> using namespace std; #define size 7 int minimumDistance(int distance[], bool visited[]) { int min = INT_MAX; int min_index = INT_MAX; for (int i = 0; i < size; i++) { if (!visited[i] & amp; & distance[i] <= min) { min = distance[i]; min_index = i; } } return min_index; } void printParentPath(int parent[], int i) { if (parent[i] == -1) { return; } printParentPath(parent, parent[i]); cout << i + 1 << " "; } void dijkstra(int graph[size][size], int source) { int distance[size]; bool visited[size]; int parent[size]; for (int i = 0; i < size; i++) { parent[0] = -1; distance[i] = INT_MAX; visited[i] = false; } distance[source] = 0; for (int i = 0; i < size - 1; i++) { int U = minimumDistance(distance, visited); visited[U] = true; for (int j = 0; j < size; j++) { int curr_distance = distance[U] + graph[U][j]; if (!visited[j] & amp; & graph[U][j] & amp; & curr_distance < distance[j]) { parent[j] = U; distance[j] = curr_distance; } } } cout << "Vertex\t\tDistance\tPath" << endl; for (int i = 1; i < size; i++) { cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t" << source + 1 << " "; printParentPath(parent, i); cout << endl; } } int main() { int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0}, {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0}, {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3}, {0, 0, 0, 0, 5, 3, 0}}; dijkstra(graph, 0); }
आउटपुट:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python कार्यान्वयन डिज्कस्ट्रा एल्गोरिथ्म
डिज्कस्ट्रा के एल्गोरिथ्म को लागू करने के लिए अजगर, कोड यह है:
num_of_vertex = 7 def minimumDistance(distance, visited): _min = 1e11 min_index = 1e11 for i in range(num_of_vertex): if not visited[i] and distance[i] & lt; = _min: _min = distance[i] min_index = i return min_index def printParentNode(parent, i): if parent[i] == -1: return printParentNode(parent, parent[i]) print("{} ".format(i + 1), end = "") def dijkstra(graph, src): distance = list() visited = list() parent = list() for i in range(num_of_vertex): parent.append(-1) distance.append(1e11) visited.append(False) distance[src] = 0 for i in range(num_of_vertex - 1): U = minimumDistance(distance, visited) visited[U] = True for j in range(num_of_vertex): curr_distance = distance[U] + graph[U][j] if not visited[j] and graph[U][j] and curr_distance & lt; distance[j]: parent[j] = U distance[j] = curr_distance print("Vertex\t\tDistance\tPath") for i in range(num_of_vertex): print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end = "") printParentNode(parent, i) print("") graph = [ [0, 1, 7, 6, 0, 0, 0], [1, 0, 9, 0, 0, 3, 0], [7, 9, 0, 0, 0, 0, 1], [6, 0, 0, 0, 2, 0, 0], [0, 0, 0, 2, 0, 0, 0], [0, 3, 0, 0, 0, 0, 3], [0, 0, 0, 0, 5, 3, 0] ] dijkstra(graph, 0)
आउटपुट:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
हम देख सकते हैं कि एल्गोरिथ्म स्रोत नोड से न्यूनतम दूरी की गणना करता है।
डिज्कस्ट्रा एल्गोरिथ्म का अनुप्रयोग
डिज्कस्ट्रा एल्गो के कई उपयोग हैं। इनमें से, नेटवर्किंग के क्षेत्र में इसका व्यापक रूप से उपयोग किया जाता है। डिज्कस्ट्रा के एल्गोरिथम के कुछ वास्तविक उपयोग इस प्रकार हैं:
गूगल मानचित्र में डिज्कस्ट्रा: मूलतः, यह एल्गोरिथ्म सबसे छोटे रास्ते खोजने के लिए रीढ़ की हड्डी है। जैसा कि हम ऊपर दिए गए कोड स्निपेट आउटपुट से देख सकते हैं।
Google सरल डिज्कस्ट्रा एल्गोरिदम का उपयोग नहीं करता है। इसके बजाय, यह एक संशोधित संस्करण का उपयोग करता है। जब आप कोई गंतव्य चुनते हैं, तो यह आपको Google मानचित्र में कई रास्ते दिखाता है। इन रास्तों में से, कुछ रास्ते उपयोगकर्ता के लिए छांटे गए हैं। चुने गए ये रास्ते "समय" पर आधारित हैं। इसलिए, "समय" सबसे छोटे रास्ते के लिए एक एज कॉस्ट है।
आईपी रूटिंग में डिज्कस्ट्रा: आईपी रूटिंग एक नेटवर्किंग शब्दावली है। इसका मतलब है कि आपका डेटा पैकेट रिसीवर को अलग-अलग रास्तों से कैसे भेजा जा रहा है। इन रास्तों में राउटर, सर्वर आदि शामिल हैं। आईपी रूटिंग में, विभिन्न प्रकार के प्रोटोकॉल होते हैं।
ये प्रोटोकॉल राउटर को डेटा भेजने के लिए सबसे छोटे रास्ते खोजने में मदद करते हैं। प्रोटोकॉल का एक नाम "OSPF (ओपन शॉर्टेस्ट पाथ फर्स्ट)" है। OSPF डिज्कस्ट्रा एल्गोरिदम का उपयोग करता है। राउटर रूट्स की एक तालिका बनाए रखता है। प्रत्येक राउटर अपने टेबल को पड़ोसी राउटर के साथ साझा करता है। अपडेट की गई तालिका प्राप्त करने के बाद, उन्हें फिर से सभी रास्तों की गणना करनी चाहिए। उस समय, राउटर डिज्कस्ट्रा एल्गोरिदम का उपयोग करता है।
डिज्कस्ट्रा के एल्गोरिथ्म की सीमाएँ
डिज्कस्ट्रा एल्गोरिथ्म नकारात्मक किनारे ग्राफ में सबसे छोटे पथ की गारंटी नहीं दे सकता है। डिज्कस्ट्रा एल्गोरिथ्म इन पद्धतियों का पालन करता है:
- एक नोड से दूसरे नोड तक एक सबसे छोटा रास्ता लिया जाएगा।
- एक बार दो नोड्स के बीच सबसे छोटा रास्ता चुन लिया जाए तो उसकी गणना दोबारा नहीं की जाएगी।
यहां, नकारात्मक किनारों वाले दो उदाहरणों पर ध्यान दें।
बायें ग्राफ़ में, तीन कोने हैं। डिज्कस्ट्रा ग्राफ पर निम्नलिखित तरीके से चलेगा:
चरण 1) आरंभिक शीर्ष "1" को शून्य पर आरंभीकृत किया जाएगा। अन्य नोड्स में अनंतता होगी।
चरण 2) नोड “1” को विज़िट किए गए के रूप में चिह्नित करें और इसे सबसे छोटे पथ में शामिल करें।
चरण 3) स्रोत नोड 1 से नोड “2” और “3” की दूरी अनंत पर सेट की गई है, क्योंकि सबसे छोटा रास्ता अभी तक गणना नहीं किया गया है। इसलिए, कोई भी रास्ता जिसकी लागत अनंत से कम होगी उसे सबसे छोटे रास्ते में जोड़ दिया जाएगा (लालची दृष्टिकोण)।
चरण 4) स्रोत शीर्ष या स्रोत नोड “1” से “2” तक की दूरी को अपडेट करना। वर्तमान वजन 5 (5) होगा
चरण 5) अब यदि हम नोड “1” से सबसे छोटी दूरी की जाँच करें, तो हम पाते हैं कि 5 किनारा 1–> 2 के लिए सबसे छोटी दूरी है। इसलिए, नोड “2” को विज़िट किया गया के रूप में चिह्नित किया जाएगा।
इसी प्रकार, नोड “3” को भी विज़िट किया गया के रूप में चिह्नित किया जाएगा क्योंकि सबसे छोटी दूरी 3 है।
हालाँकि, अगर हम देखें, तो 1-3-2 का एक रास्ता है जिसकी लागत केवल 2 होगी। लेकिन डिज्कस्ट्रा दिखाता है कि नोड “1” से नोड “2” तक, सबसे छोटी दूरी 5 है। इसलिए, डिज्कस्ट्रा सबसे छोटी दूरी की सही गणना करने में विफल रहा। ऐसा होने का कारण यह है कि, डिज्कस्ट्रा एक लालची एल्गोरिथम है। इसलिए, एक बार जब नोड को विज़िट किया गया चिह्नित किया जाता है, तो उस पर पुनर्विचार नहीं किया जाएगा, हालाँकि एक छोटा रास्ता उपलब्ध हो सकता है। यह समस्या केवल तब होती है जब किनारों पर नकारात्मक लागत या नकारात्मक भार किनारे होते हैं
इस परिदृश्य में डिज्कस्ट्रा दो नोड्स के बीच सबसे छोटे रास्ते की गणना करने में विफल रहता है। परिणामस्वरूप, इस एल्गोरिथ्म में कुछ कमियाँ हैं। इस नकारात्मक किनारे की समस्या को हल करने के लिए, "बेलमैन-फ़ोर्ड एल्गोरिथ्म" नामक एक अन्य एल्गोरिथ्म का उपयोग किया जाता है। वह एल्गोरिथ्म नकारात्मक किनारों के साथ काम कर सकता है।
डिज्कस्ट्रा का एल्गोरिथ्म जटिलता
उपरोक्त कार्यान्वयन में दो "फॉर" लूप का उपयोग किया गया। ये लूप शीर्षों की संख्या के लिए चलते हैं। इसलिए, समय जटिलता है ओ(वी2)यहाँ, शब्द "0" का अर्थ एक संकेतन है जो डिज्कस्ट्रा एल्गोरिथम के लिए एक धारणा देता है।
हम "प्राथमिकता कतार" का उपयोग करके ग्राफ को संग्रहीत कर सकते हैं। प्राथमिकता कतार एक बाइनरी हीप डेटा संरचना है। यह 2D मैट्रिक्स की तुलना में अधिक कुशल होगी। जिस किनारे पर न्यूनतम लागत होगी, उसकी प्राथमिकता उच्च होगी।
तो समय जटिलता होगी ओ(ई लॉग(वी))यहाँ, E किनारों की संख्या है, और V शीर्षों की संख्या है।
अंतरिक्ष जटिलता है ओ(वी2), क्योंकि हम एक आसन्न मैट्रिक्स का उपयोग कर रहे हैं (2डी सरणी) आसन्न सूची या कतार डेटा संरचना का उपयोग करके स्थान जटिलता को अनुकूलित किया जा सकता है।