ऑल-पेयर्स शॉर्टेस्ट पाथ (फ्लॉयड-वार्शल एल्गोरिदम)

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

सबसे पहले आउटपुट मैट्रिक्स ग्राफ के दिए गए कॉस्ट मैट्रिक्स के समान होता है। उसके बाद आउटपुट मैट्रिक्स को सभी वर्टेक्स 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)

इनपुट − दिए गए ग्राफ का कॉस्ट मैट्रिक्स।

आउटपुट − किसी भी वर्टेक्स से किसी भी वर्टेक्स तक शॉर्टेस्ट पाथ के लिए मैट्रिक्स।

Begin
    for k := 0 to n, do
        for i := 0 to n, do
            for j := 0 to n, do
                if cost[i,k] + cost[k,j] < cost[i,j], then
                    cost[i,j] := cost[i,k] + cost[k,j]
                done
            done
        done
    वर्तमान कॉस्ट मैट्रिक्स प्रदर्शित करें
End

उदाहरण (C++)

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