सिंगल-सोर्स शॉर्टेस्ट पाथ, नॉन-नेगेटिव वेट (डिज्क्स्ट्रा एल्गोरिदम)

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

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

इनपुट − एडजेसेंसी मैट्रिक्स −

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

आउटपुट −

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
    चुने गए नोड की वर्तमान स्थिति रखने के लिए एक स्टेटस लिस्ट बनाएं
    V में सभी वर्टेक्स u के लिए do
        status[u] := अनकंसीडर्ड
        dist[u] := कॉस्ट मैट्रिक्स का उपयोग करके सोर्स से दूरी
        next[u] := स्टार्ट
    done
    status[स्टार्ट] := कंसीडर्ड, dist[स्टार्ट] := 0 और next[स्टार्ट] := φ
    जबकि अनकंसीडर्ड वर्टेक्स u को लें जिसकी दूरी न्यूनतम है do
        status[u] := कंसीडर्ड
        V में सभी वर्टेक्स v के लिए do
            यदि status[v] = अनकंसीडर्ड तो
                यदि dist[v] > dist[u] + cost[u,v] तो
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
                done
            done
        done
End

उदाहरण (C++)

#include 
#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