आसन्न सूची प्रतिनिधित्व के लिए दिज्क्स्ट्रा का एल्गोरिदम

एक दिया गया ग्राफ़ G(V, E) है, जिसकी आसन्न सूची निरूपण के साथ है, और एक स्रोत शीर्ष भी प्रदान किया गया है। ग्राफ़ जी के किसी अन्य शीर्ष से स्रोत शीर्ष के बीच न्यूनतम सबसे छोटा पथ खोजने के लिए डिजस्ट्रा का एल्गोरिदम।

इस समस्या को हल करने के लिए, हम दो सूचियों का उपयोग करेंगे। एक कोने को स्टोर करना है जिसे सबसे छोटा पथ वृक्ष माना जाता है, और दूसरा उन शिखरों को धारण करेगा जिन पर अभी तक विचार नहीं किया गया है। एल्गोरिथम के प्रत्येक चरण में, हम बिना सोचे-समझे शीर्ष पाते हैं और जिसकी स्रोत से न्यूनतम दूरी होती है।

पूर्ववर्ती नोड को रखने के लिए एक अन्य सूची का उपयोग किया जाता है। पूर्ववर्ती नोड का उपयोग करके, हम स्रोत और गंतव्य से पथ ढूंढ सकते हैं।

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

इनपुट और आउटपुट

Input:
The adjacency list of the graph with the cost of each edge.

Output:
0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

एल्गोरिदम

dijkstraShortestPath(g : Graph, dist, prev, start : node)

इनपुट - ग्राफ़ जी, दूरी स्टोर करने के लिए जिला सूची, पूर्ववर्ती नोड्स के लिए पिछली सूची, और शीर्ष प्रारंभ करें।

आउटपुट - प्रारंभ से अन्य सभी शीर्षों तक का सबसे छोटा पथ।

Begin
   for all vertices u in (V - start) do
      dist[u] := ∞
      prev[u] := φ
   done

   set dist[start] = 0 and prev[start] := φ

   for all node u in V do
      insert u into queue ‘Q’.
   done

   while Q is not empty do
      u := minimum element from Queue
      delete u from Q
      insert u into set S

      for each node v adjacent with node u do
         if dist[u]+cost(v) < dist[v] then
            dist[v] := dist[u]+cost(v)
            prev[v] := u
      done
   done
End

उदाहरण

#include<iostream>
#include<set>
#include<list>
#include<algorithm>
using namespace std;

typedef struct nodes {
   int dest;
   int cost;
}node;

class Graph {
   int n;
   list<node> *adjList;
   private:
      void showList(int src, list<node> lt) {
         list<node> :: iterator i;
         node tempNode;

         for(i = lt.begin(); i != lt.end(); i++) {
            tempNode = *i;
            cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
         }
         cout << endl;
      }
   public:
      Graph() {
         n = 0;
      }

      Graph(int nodeCount) {
         n = nodeCount;
         adjList = new list<node>[n];
      }

      void addEdge(int source, int dest, int cost) {
         node newNode;
         newNode.dest = dest;
         newNode.cost = cost;
         adjList[source].push_back(newNode);
      }

      void displayEdges() {
         for(int i = 0; i<n; i++) {
            list<node> tempList = adjList[i];
            showList(i, tempList);
         }
      }

      friend void dijkstra(Graph g, int *dist, int *prev, int start);
};

void dijkstra(Graph g, int *dist, int *prev, int start) {
   int n = g.n;

   for(int u = 0; u<n; u++) {
      dist[u] = 9999;   //set as infinity
      prev[u] = -1;    //undefined previous
   }

   dist[start] = 0;   //distance of start is 0
   set<int> S;       //create empty set S
   list<int> Q;

   for(int u = 0; u<n; u++) {
      Q.push_back(u);    //add each node into queue
   }

   while(!Q.empty()) {
      list<int> :: iterator i;
      i = min_element(Q.begin(), Q.end());
      int u = *i; //the minimum element from queue
      Q.remove(u);
      S.insert(u); //add u in the set
      list<node> :: iterator it;

      for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
         if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
            dist[it->dest] = (dist[u]+(it->cost));
            prev[it->dest] = u;
         }
      }
   }
}

main() {
   int n = 7;
   Graph g(n);
   int dist[n], prev[n];
   int start = 0;

   g.addEdge(0, 1, 3);
   g.addEdge(0, 2, 6);
   g.addEdge(1, 0, 3);
   g.addEdge(1, 2, 2);
   g.addEdge(1, 3, 1);
   g.addEdge(2, 1, 6);
   g.addEdge(2, 1, 2);
   g.addEdge(2, 3, 1);
   g.addEdge(2, 4, 4);

   g.addEdge(2, 5, 2);
   g.addEdge(3, 1, 1);
   g.addEdge(3, 2, 1);
   g.addEdge(3, 4, 2);
   g.addEdge(3, 6, 4);
   g.addEdge(4, 2, 4);
   g.addEdge(4, 3, 2);
   g.addEdge(4, 5, 2);
   g.addEdge(4, 6, 1);
   g.addEdge(5, 2, 2);
   g.addEdge(5, 4, 2);
   g.addEdge(5, 6, 1);
   g.addEdge(6, 3, 4);
   g.addEdge(6, 4, 1);
   g.addEdge(6, 5, 1);

   dijkstra(g, dist, prev, start);

   for(int i = 0; i<n; i++)
      if(i != start)
         cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
}

आउटपुट

0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4