डिज्क्स्ट्रा का सबसे छोटा पथ एल्गोरिदम

मुख्य समस्या पिछले जैसी ही है, प्रारंभिक नोड से किसी अन्य नोड तक, सबसे छोटी दूरियां ढूंढें। इस समस्या में, मुख्य अंतर यह है कि ग्राफ को एडजेसेंसी मैट्रिक्स का उपयोग करके दर्शाया गया है। (कॉस्ट मैट्रिक्स और एडजेसेंसी मैट्रिक्स इस उद्देश्य के लिए समान हैं)।

एडजेसेंसी लिस्ट प्रतिनिधित्व के लिए, टाइम कॉम्प्लेक्सिटी O(V^2) है जहां V ग्राफ G(V, E) में नोड्स की संख्या है।

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

इनपुट: एडजेसेंसी मैट्रिक्स: 
आउटपुट:
0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7

एल्गोरिदम

dijkstraShortestPath(n, dist, next, start)

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

Begin
    चयनित नोड की वर्तमान स्थिति रखने के लिए एक स्टेटस लिस्ट बनाएं
    for all vertices u in V do
        status[u] := unconsidered
        dist[u] := कॉस्ट मैट्रिक्स का उपयोग करके सोर्स से दूरी
        next[u] := start
    done
    status[start] := considered, dist[start] := 0 and next[start] := ∅
    while take unconsidered vertex u as distance is minimum do
        status[u] := considered
        for all vertex v in V do
            if status[v] = unconsidered then
                if dist[v] > dist[u] + cost[u,v] then
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
            done
        done
    done
End

उदाहरण

#include <iostream>
#define V 7
#define INF 999
using namespace std;

// ग्राफ का कॉस्ट मैट्रिक्स
int costMat[V][V] = {
    {0, 3, 6, INF, INF, INF, INF},
    {3, 0, 2, 1, INF, INF, INF},
    {6, 2, 0, 1, 4, 2, INF},
    {INF, 1, 1, 0, 2, INF, 4},
    {INF, INF, 4, 2, 0, 2, 1},
    {INF, INF, 2, INF, 2, 0, 1},
    {INF, INF, INF, 4, 1, 1, 0}
};

int minimum(int *status, int *dis, int n) {
    int i, min, index;
    min = INF;
    for(i = 0; i < n; i++)
        if(dis[i] < min && status[i] == 1) {
            min = dis[i];
            index = i;
        }
    if(status[index] == 1)
        return index; // न्यूनतम अनकंसीडर्ड वर्टेक्स डिस्टेंस
    else
        return -1; // जब सभी वर्टेक्स कंसीडर्ड हो जाएं
}

void dijkstra(int n, int *dist, int *next, int s) {
    int status[V];
    int u, v;
    // इनिशियलाइज़ेशन
    for(u = 0; u < n; u++) {
        status[u] = 1; // अनकंसीडर्ड वर्टेक्स
        dist[u] = costMat[u][s]; // सोर्स से दूरी
        next[u] = s;
    }
    // सोर्स वर्टेक्स के लिए
    status[s] = 2; dist[s] = 0; next[s] = -1; // -1 स्टार्टिंग वर्टेक्स के लिए
    while((u = minimum(status, dist, n)) > -1) {
        status[u] = 2; // अब कंसीडर्ड
        for(v = 0; v < n; v++)
            if(status[v] == 1)
                if(dist[v] > dist[u] + costMat[u][v]) {
                    dist[v] = dist[u] + costMat[u][v]; // दूरी अपडेट करें
                    next[v] = u;
                }
    }
}

int main() {
    int dis[V], next[V], i, start = 0;
    dijkstra(V, dis, next, start);
    for(i = 0; i < V; i++)
        if(i != start)
            cout << start << " to " << i << ", Using: " << next[i] << ", Cost: " << dis[i] << endl;
}

आउटपुट

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