फ्लॉयड वार्शल एल्गोरिदम

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

सबसे पहले, आउटपुट मैट्रिक्स ग्राफ के दिए गए कॉस्ट मैट्रिक्स के समान होता है। उसके बाद, सभी वर्टेक्स k को इंटरमीडिएट वर्टेक्स के रूप में उपयोग करके आउटपुट मैट्रिक्स को अपडेट किया जाएगा।

इस एल्गोरिदम की समय जटिलता O(V³) है, जहां V ग्राफ में वर्टेक्स की संख्या है।

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

इनपुट: ग्राफ का कॉस्ट मैट्रिक्स
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 3 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0

एल्गोरिदम

floydWarshal(cost)

इनपुट: दिए गए ग्राफ का कॉस्ट मैट्रिक्स
आउटपुट: किसी भी वर्टेक्स से किसी भी वर्टेक्स तक सबसे छोटे पथ के लिए मैट्रिक्स

शुरुआत
    k := 0 से n तक, करें
        i := 0 से n तक, करें
            j := 0 से n तक, करें
                यदि cost[i,k] + cost[k,j] < cost[i,j], तो
                    cost[i,j] := cost[i,k] + cost[k,j]
            पूर्ण
        पूर्ण
    पूर्ण
    वर्तमान कॉस्ट मैट्रिक्स प्रदर्शित करें
अंत

उदाहरण (C++ कोड)

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

int costMat[NODE][NODE] = {
    {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}
};

void floydWarshal() {
    int cost[NODE][NODE];
    for(int i = 0; i < NODE; i++)
        for(int j = 0; j < NODE; j++)
            cost[i][j] = costMat[i][j];
    
    for(int k = 0; k < NODE; k++) {
        for(int i = 0; i < NODE; i++)
            for(int j = 0; j < NODE; j++)
                if(cost[i][k] + cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k] + cost[k][j];
    }
    
    cout << "The matrix:" << endl;
    for(int i = 0; i < NODE; i++) {
        for(int j = 0; j < NODE; j++)
            cout << setw(3) << cost[i][j];
        cout << endl;
    }
}

int main() {
    floydWarshal();
}

आउटपुट

The matrix:
  0  3  5  4  6  7  7
  3  0  2  1  3  4  4
  5  2  0  1  3  2  3
  4  1  1  0  2  3  3
  6  3  3  2  0  2  1
  7  4  2  3  2  0  1
  7  4  3  3  1  1  0