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

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

डिज्क्स्ट्रा एल्गोरिदम (Dijkstra's Shortest Path First Algorithm, SPF Algorithm) ग्राफ में नोड्स के बीच सबसे छोटे पथ ढूंढने का एक एल्गोरिदम है, जो उदाहरण के लिए रोड नेटवर्क को दर्शा सकता है। एल्गोरिदम प्रारंभिक वर्टेक्स (स्रोत) से ग्राफ में अन्य सभी बिंदुओं तक सबसे छोटे पथों का एक ट्री बनाता है।

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

ग्राफ घटक

• वर्टेक्स/नोड्स - एल्गोरिदम में v या u द्वारा दर्शाए जाते हैं
• वेटेड एजेस - दो नोड्स को जोड़ते हैं: (u,v) एक एज दर्शाता है, और w(u,v) इसका वजन दर्शाता है

एल्गोरिदम चरण

1. सभी वर्टेक्स की दूरी = अनंत पर सेट करें, सिवाय स्रोत वर्टेक्स के, स्रोत की दूरी = 0 सेट करें
2. स्रोत वर्टेक्स को मिन-प्रायोरिटी क्यू में (दूरी, वर्टेक्स) के रूप में डालें
3. प्रायोरिटी क्यू से न्यूनतम दूरी वाले वर्टेक्स को पॉप करें (पहले पॉप किया गया वर्टेक्स = स्रोत)
4. पॉप किए गए वर्टेक्स से जुड़े वर्टेक्स की दूरियों को अपडेट करें यदि "वर्तमान वर्टेक्स दूरी + एज वजन < अगला वर्टेक्स दूरी", फिर नई दूरी के साथ वर्टेक्स को प्रायोरिटी क्यू में डालें
5. यदि पॉप किया गया वर्टेक्स पहले विजिट किया गया है, तो इसे उपयोग किए बिना जारी रखें
6. प्रायोरिटी क्यू खाली होने तक समान एल्गोरिदम लागू करें

इनपुट

G[max][max] = {{0,1,0,3,10},
               {1,0,5,0,0},
               {0,5,0,2,1},
               {3,0,2,0,6},
               {10,0,1,6,0}}
n=5, u=0

आउटपुट

Distance of node1=1 Path=1<-0
Distance of node2=5 Path=2<-3<-0
Distance of node3=3 Path=3<-0
Distance of node4=6 Path=4<-2<-3<-0

उदाहरण

#include <iostream>
#include <stdio.h>
#include <climits>
using namespace std;

#define INFINITY 9999
#define MAX 5

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main() {
    int G[MAX][MAX] = {{0,1,0,3,10},
                       {1,0,5,0,0},
                       {0,5,0,2,1},
                       {3,0,2,0,6},
                       {10,0,1,6,0}};
    int n = 5;
    int u = 0;
    dijkstra(G, n, u);
    return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode) {
    int cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, mindistance, nextnode, i, j;

    // कॉस्ट मैट्रिक्स बनाएं
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            if(G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];

    // इनिशियलाइज़ेशन
    for(i = 0; i < n; i++) {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;

    while(count < n - 1) {
        mindistance = INFINITY;
        // न्यूनतम दूरी वाला अनविजिटेड वर्टेक्स ढूंढें
        for(i = 0; i < n; i++)
            if(distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }

        visited[nextnode] = 1;

        // शेष वर्टेक्स की दूरी अपडेट करें
        for(i = 0; i < n; i++)
            if(!visited[i])
                if(mindistance + cost[nextnode][i] < distance[i]) {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }

    // परिणाम प्रिंट करें
    for(i = 0; i < n; i++)
        if(i != startnode) {
            cout << "\nDistance of node " << i << " = " << distance[i];
            cout << "\nPath = " << i;
            j = i;
            do {
                j = pred[j];
                cout << " <- " << j;
            } while(j != startnode);
        }
}

जटिलता विश्लेषण

आवेदन

• GPS नेविगेशन सिस्टम
• नेटवर्क रूटिंग प्रोटोकॉल (OSPF, IS-IS)
• सोशल नेटवर्क में सबसे छोटा पथ
• संसाधन आवंटन समस्याएं