डाइक्स्ट्रा का एल्गोरिदम Python & C++ (उदाहरण)

सबसे छोटा रास्ता या सबसे छोटी दूरी क्या है?

स्रोत शीर्ष से गंतव्य शीर्ष तक का वह पथ जिसकी लागत न्यूनतम हो, सबसे छोटा पथ या सबसे कम दूरी कहलाता है। ग्राफ सिद्धांत में, स्रोत से गंतव्य तक कई पथ हो सकते हैं। इन पथों में से, यदि कोई ऐसा पथ है जिसकी लागत न्यूनतम हो, तो उसे सबसे छोटा पथ कहते हैं।

यहां "लागत" से तात्पर्य मार्ग में नोड्स की संख्या या प्रत्येक किनारे पर लागतों के योग से है। एक पथ में एक या एक से अधिक किनारे हो सकते हैं। दो शीर्षों के बीच के संबंध को "किनारा" कहा जाता है। सबसे छोटे पथ के कई एल्गोरिदम हैं, जैसे डाइक्स्ट्रा एल्गोरिदम और बेलमैन-फोर्ड एल्गोरिदम।

यहां हम डाइक्स्ट्रा एल्गोरिदम पर चर्चा करेंगे। आइए निम्नलिखित भारित ग्राफ को देखें:

एक अनिर्देशित-भारित ग्राफ

• "भारित" शब्द का अर्थ है एक नोड से दूसरे नोड तक जाने की लागत। उदाहरण के लिए, नोड 1 से नोड 2 तक जाने की लागत या भार 1 है।
• नोड 1 और नोड 2 के बीच के पथ को किनारा (एज) कहा जाता है।
• “अनिर्देशित” का अर्थ है कि आप एक नोड से दूसरे नोड तक जा सकते हैं और वापस पहले वाले नोड पर आ सकते हैं। इसलिए, यदि हम नोड 1 से नोड 7 तक के सभी मार्गों को खोजने का प्रयास करें, तो वे इस प्रकार होंगे:

इन चार मार्गों में से, हम देख सकते हैं कि पहले मार्ग की लागत 7 है। अतः, लागत के लिहाज से यह सबसे छोटा मार्ग है।

सबसे छोटा रास्ता

डिज्कस्ट्रा का एल्गोरिदम कैसे काम करता है

डिज्क्स्ट्रा एल्गोरिदम निर्देशित और अनिर्देशित भारित ग्राफ़ दोनों में सबसे कम दूरी ज्ञात कर सकता है। यह एल्गोरिदम लालची है क्योंकि यह हमेशा मूल बिंदु से सबसे छोटे या निकटतम नोड का चयन करता है। "लालची" शब्द का अर्थ है कि परिणामों के एक समूह में से, एल्गोरिदम सर्वोत्तम परिणाम का चयन करेगा।

यहां, हम सभी मार्गों में से सबसे छोटा मार्ग खोजने का प्रयास कर रहे हैं। इसलिए, डाइक्स्ट्रा एल्गोरिदम एक ही स्रोत नोड से सभी सबसे छोटे मार्गों को ढूंढता है। परिणामस्वरूप, यह एक लालची एल्गोरिथ्म.

नीचे दिए गए "उदाहरण" अनुभाग में, आपको चरण-दर-चरण प्रक्रिया दिखाई देगी। यह इस प्रकार काम करती है:

चरण 1) आरंभिक नोड को 0 लागत से और शेष नोड्स को अनंत लागत से आरंभ करें।
चरण 2) एक ऐरे या सूची बनाए रखें tracविज़िट किए गए नोड्स का k।
चरण 3) नोड की लागत को न्यूनतम लागत से अपडेट करें। यह वर्तमान लागत की तुलना पथ की लागत से करके किया जा सकता है (उदाहरण अनुभाग में दिखाया गया है)।
चरण 4) सभी नोड्स का दौरा हो जाने तक चरण 3 को जारी रखें।

इन सभी चरणों को पूरा करने के बाद, हम स्रोत से गंतव्य तक न्यूनतम लागत वाला मार्ग खोज लेंगे।

डिज्कस्ट्रा और बीएफएस, डीएफएस के बीच अंतर

डिज्क्स्ट्रा और बीएफएस-डीएफएस के बीच मुख्य अंतर यह है कि डिज्क्स्ट्रा सबसे छोटा पथ खोजने वाला एल्गोरिदम है, जबकि बीएफएस और डीएफएस सामान्य पथ खोजने वाले एल्गोरिदम हैं। सामान्य तौर पर, बीएफएस और डीएफएस पथ खोजते समय किनारे की लागत पर विचार नहीं करते हैं। इसलिए, ये एल्गोरिदम सबसे छोटे पथ की गारंटी नहीं दे सकते।

बीएफएस कैसे काम करता है, इसका 2डी ग्रिड प्रदर्शन

एल्गोस्केच, बीएफएस प्रदर्शन दिखा रहा है

यह प्रदर्शन दर्शाता है कि BFS केवल पथ ढूँढता है। हालाँकि, यह पथ के भार की परवाह नहीं करता है। BFS (पहले चौड़ाई खोजो) यह मानता है कि एक नोड से दूसरे नोड तक यात्रा करने में केवल 1 का खर्च आएगा।

आइए एक उदाहरण ग्राफ देखें:

यहां, बीएफएस स्तर 2 में एक पथ ढूंढता है। बीएफएस ग्राफ को स्तर क्रम में पार करता है। इसलिए, यह इस प्रकार यात्रा करता है:

चरण 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 किनारों की संख्या के आधार पर पथ लागत की गणना करता है। 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" को विज़िट किया हुआ चिह्नित नहीं किया गया था क्योंकि हम नोड "6" से नोड "7" तक पहुँच सकते हैं। पथ "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 होगी।

उपनाम Code डाइक्स्ट्रा का एल्गोरिदम

डाइक्स्ट्रा एल्गोरिदम का स्यूडो-कोड यहाँ दिया गया है:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- 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] && 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] && graph[U][j] &&
          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 डाइक्स्ट्रा एल्गोरिदम का कार्यान्वयन

डिज्कस्ट्रा के एल्गोरिथ्म को लागू करने के लिए 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] <= _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 < 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

हम देख सकते हैं कि एल्गोरिदम स्रोत नोड से सबसे कम दूरी की गणना करता है।

डिज्कस्ट्रा एल्गोरिथ्म का अनुप्रयोग

डिज्क्स्ट्रा एल्गोरिदम के कई उपयोग हैं। इनमें से एक प्रमुख उपयोग नेटवर्किंग के क्षेत्र में होता है। डिज्क्स्ट्रा एल्गोरिदम के कुछ वास्तविक जीवन के उपयोग इस प्रकार हैं:

गूगल मैप्स में डिज्क्स्ट्रा: यह एल्गोरिदम सबसे छोटे रास्तों को खोजने का आधार है, जैसा कि हम ऊपर दिए गए कोड स्निपेट आउटपुट से देख सकते हैं।

गूगल सरल डाइक्स्ट्रा एल्गोरिदम का उपयोग नहीं करता है। इसके बजाय, यह एक संशोधित संस्करण का उपयोग करता है। जब आप गंतव्य का चयन करते हैं, तो गूगल मैप्स में आपको कई रास्ते दिखाई देते हैं। इन रास्तों में से कुछ को उपयोगकर्ता के लिए क्रमबद्ध किया जाता है। इन रास्तों का चयन "समय" के आधार पर किया जाता है। इसलिए, "समय" सबसे छोटे रास्ते के लिए एज कॉस्ट है।

आईपी ​​राउटिंग में डाइक्स्ट्रा: आईपी ​​रूटिंग आईपी ​​राउटिंग नेटवर्किंग की शब्दावली है। यह बताती है कि आपका डेटा पैकेट विभिन्न मार्गों से रिसीवर तक कैसे पहुंचाया जाता है। इन मार्गों में राउटर, सर्वर और अन्य उपकरण शामिल होते हैं। आईपी राउटिंग में विभिन्न प्रकार के प्रोटोकॉल होते हैं।

ये प्रोटोकॉल राउटर को डेटा भेजने के लिए सबसे छोटे रास्ते खोजने में मदद करते हैं। इनमें से एक प्रोटोकॉल का नाम "OSPF (ओपन शॉर्टेस्ट पाथ फर्स्ट)" है। OSPF डाइक्स्ट्रा एल्गोरिदम का उपयोग करता है। राउटर रास्तों की एक तालिका रखता है। प्रत्येक राउटर अपनी तालिका पड़ोसी राउटरों के साथ साझा करता है। अद्यतन तालिका प्राप्त करने के बाद, उन्हें सभी रास्तों की दोबारा गणना करनी होती है। उस समय, राउटर डाइक्स्ट्रा एल्गोरिदम का उपयोग करता है।

डिज्कस्ट्रा के एल्गोरिथ्म की सीमाएँ

डिज्क्स्ट्रा एल्गोरिदम नकारात्मक किनारों वाले ग्राफ में सबसे छोटे पथ की गारंटी नहीं दे सकता। डिज्क्स्ट्रा एल्गोरिदम निम्नलिखित सिद्धांतों का पालन करता है:

• एक नोड से दूसरे नोड तक एक सबसे छोटा रास्ता लिया जाएगा।
• एक बार दो नोड्स के बीच सबसे छोटा रास्ता चुन लिया जाए तो उसकी गणना दोबारा नहीं की जाएगी।

यहां, नकारात्मक किनारों वाले दो उदाहरणों पर ध्यान दें।

बाएं ग्राफ में, इसमें तीन शीर्ष हैं। डाइक्स्ट्रा ग्राफ पर निम्न प्रकार से चलेगा:

चरण 1) आरंभिक शीर्ष "1" को शून्य पर आरंभीकृत किया जाएगा। अन्य नोड्स में अनंतता होगी।

चरण 2) नोड “1” को विज़िट किया गया के रूप में चिह्नित करें और इसे सबसे छोटे पथ में शामिल करें।

चरण 3) स्रोत नोड 1 से नोड "2" और "3" की दूरी अनंत निर्धारित की गई है, क्योंकि सबसे छोटा पथ अभी तक गणना नहीं किया गया है। इसलिए, अनंत से कम समय लेने वाले किसी भी पथ को सबसे छोटे पथ में जोड़ा जाएगा (लालची दृष्टिकोण)।

चरण 4) स्रोत शीर्ष "1" से "2" तक की दूरी को अपडेट किया जा रहा है। वर्तमान भार 5 होगा (5 < अनंत)। इसी प्रकार, नोड "1" से "3" तक की दूरी को भी 3 के भार के साथ अपडेट किया जा रहा है।

चरण 5) अब यदि हम नोड “1” से सबसे छोटी दूरी की जाँच करें, तो हम पाते हैं कि किनारे 1→2 के लिए सबसे छोटी दूरी 5 है। इसलिए, नोड “2” को विज़िट किया गया के रूप में चिह्नित किया जाएगा। इसी प्रकार, नोड “3” को भी विज़िट किया गया के रूप में चिह्नित किया जाएगा क्योंकि सबसे छोटी दूरी 3 है।

हालांकि, अगर हम गौर करें तो एक पथ 1-3-2 है जिसकी लागत केवल 2 है। लेकिन डाइक्स्ट्रा दर्शाता है कि नोड "1" से नोड "2" तक की सबसे छोटी दूरी 5 है। इसलिए, डाइक्स्ट्रा सबसे छोटी दूरी की गणना सही ढंग से करने में विफल रहा। इसका कारण यह है कि डाइक्स्ट्रा एक लालची एल्गोरिदम है। इसलिए, एक बार किसी नोड को विज़िट किया हुआ चिह्नित कर दिया जाए, तो उस पर दोबारा विचार नहीं किया जाएगा, भले ही कोई छोटा पथ उपलब्ध हो। यह समस्या केवल तब उत्पन्न होती है जब किनारों की लागत ऋणात्मक हो या उनका भार ऋणात्मक हो।

इस परिदृश्य में डाइक्स्ट्रा एल्गोरिदम दो नोड्स के बीच सबसे छोटा पथ ज्ञात करने में विफल रहता है। परिणामस्वरूप, इस एल्गोरिदम में कुछ कमियाँ हैं। इस नकारात्मक किनारे की समस्या को हल करने के लिए, "बेलमैन-फोर्ड एल्गोरिदम" नामक एक अन्य एल्गोरिदम का उपयोग किया जाता है। यह एल्गोरिदम नकारात्मक किनारों के साथ भी काम कर सकता है।

डिज्कस्ट्रा का एल्गोरिथ्म जटिलता

उपरोक्त कार्यान्वयन में दो "फॉर" लूप का उपयोग किया गया। ये लूप शीर्षों की संख्या के लिए चलते हैं। इसलिए, समय जटिलता है ओ(वी²)यहां, "O" शब्द एक संकेतन है जो डाइक्स्ट्रा एल्गोरिदम के लिए एक धारणा देता है।

हम ग्राफ को "प्रायोरिटी क्यू" का उपयोग करके स्टोर कर सकते हैं। प्रायोरिटी क्यू एक बाइनरी हीप डेटा संरचना है। यह 2D मैट्रिक्स की तुलना में अधिक कुशल होगा। न्यूनतम लागत वाले किनारे को उच्च प्राथमिकता मिलेगी। तब समय जटिलता होगी ओ(ई लॉग वी)यहाँ, E किनारों की संख्या है, और V शीर्षों की संख्या है।

अंतरिक्ष जटिलता है ओ(वी²), क्योंकि हम एक आसन्न मैट्रिक्स का उपयोग कर रहे हैं (2डी सरणी) आसन्न सूची या कतार डेटा संरचना का उपयोग करके स्थान जटिलता को अनुकूलित किया जा सकता है।

अक्सर पूछे जाने वाले प्रश्न