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

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

डिज्क्स्ट्रा का एल्गोरिदम एक लालची एल्गोरिदम है जो एक ग्राफ में स्रोत शीर्ष से अन्य सभी शीर्षों तक का सबसे छोटा पथ खोजने के लिए उपयोग किया जाता है। यह भारित ग्राफ (जहां किनारों का वजन होता है) पर काम करता है और ऋणात्मक वजन वाले किनारों के लिए उपयुक्त नहीं है।

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

1. shortPath सेट बनाएं - सबसे छोटे पथ ट्री में शामिल शीर्षों को संग्रहीत करने के लिए।
2. दूरी मान आरंभ करें - सभी शीर्षों की दूरी को INFINITE (अनंत) पर सेट करें, स्रोत शीर्ष को छोड़कर जिसे 0 पर सेट करें।
3. लूप चलाएं जब तक सभी शीर्ष shortPath में शामिल न हो जाएं:
   1. अनदेखे शीर्षों में से सबसे कम दूरी वाला शीर्ष चुनें।
   2. इसे shortPath में जोड़ें।
   3. इस शीर्ष के सभी आसन्न शीर्षों की दूरी अद्यतन करें: यदि dist[u] + weight(u,v) < dist[v] हो तो dist[v] अद्यतन करें।

C प्रोग्राम कार्यान्वयन

#include <limits.h>
#include <stdio.h>
#include <stdbool.h>

#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printSolution(int dist[]) {
    printf("शीर्ष \t स्रोत से दूरी\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        { 0, 6, 0, 0, 0, 0, 0, 8, 0 },
        { 6, 0, 8, 0, 0, 0, 0, 13, 0 },
        { 0, 8, 0, 7, 0, 6, 0, 0, 2 },
        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
        { 0, 0, 6, 14, 10, 0, 2, 0, 0 },
        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
        { 0, 0, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
    };
    dijkstra(graph, 0);
    return 0;
}

आउटपुट

शीर्ष    स्रोत से दूरी
0       0
1       6
2       14
3       21
4       21
5       11
6       9
7       8
8       15

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

• समय जटिलता: O(V²) - एडजेसेंसी मैट्रिक्स प्रतिनिधित्व के लिए
• स्थान जटिलता: O(V)
• अनुकूलन: मिन-हीप का उपयोग करके O((V+E) log V) तक सुधारा जा सकता है

महत्वपूर्ण बिंदु

• केवल गैर-ऋणात्मक भार वाले ग्राफ के लिए काम करता है
• सिंगल-सोर्स शॉर्टेस्ट पथ समस्या हल करता है
• नेटवर्क रूटिंग प्रोटोकॉल (OSPF, IS-IS) में व्यापक रूप से उपयोग किया जाता है