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

एक दिया गया ग्राफ G(V, E) अपने एडजेसेंसी लिस्ट प्रतिनिधित्व के साथ है, और एक सोर्स वर्टेक्स भी प्रदान किया गया है। डिज्क्स्ट्रा का एल्गोरिदम सोर्स वर्टेक्स से ग्राफ G के किसी अन्य वर्टेक्स तक न्यूनतम सबसे छोटा पथ ढूंढने के लिए।

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

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

डिज्क्स्ट्रा के सबसे छोटे पथ एल्गोरिदम की जटिलता O(E log V) है क्योंकि ग्राफ को एडजेसेंसी लिस्ट का उपयोग करके दर्शाया गया है। यहां E एज की संख्या है, और V वर्टेक्स की संख्या है।

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

इनपुट: ग्राफ की एडजेसेंसी लिस्ट प्रत्येक एज की कॉस्ट के साथ। 
आउटपुट:
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)

इनपुट: ग्राफ g, दूरी स्टोर करने के लिए dist लिस्ट, पूर्ववर्ती नोड्स के लिए prev लिस्ट, और स्टार्ट वर्टेक्स।
आउटपुट: स्टार्ट से अन्य सभी वर्टेक्स तक सबसे छोटे पथ।

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
        u को क्यू 'Q' में इन्सर्ट करें।
    done
    while Q is not empty do
        u := Queue से न्यूनतम एलिमेंट
        u को Q से डिलीट करें
        u को सेट 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
    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; // इन्फिनिटी के रूप में सेट करें
        prev[u] = -1; // अनडिफाइंड प्रीवियस
    }
    dist[start] = 0; // स्टार्ट की दूरी 0 है
    set<int> S; // खाली सेट S बनाएं
    list<int> Q;
    for(int u = 0; u < n; u++) {
        Q.push_back(u); // प्रत्येक नोड को क्यू में जोड़ें
    }
    while(!Q.empty()) {
        list<int> :: iterator i;
        i = min_element(Q.begin(), Q.end());
        int u = *i; // क्यू से न्यूनतम एलिमेंट
        Q.remove(u);
        S.insert(u); // u को सेट में जोड़ें
        list<node> :: iterator it;
        for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
            if((dist[u] + (it->cost)) < dist[it->dest]) { // रिलैक्स (u,v)
                dist[it->dest] = (dist[u] + (it->cost));
                prev[it->dest] = u;
            }
        }
    }
}

int 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, 0, 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