অল-পেয়ার শর্টেস্ট পাথস (ফ্লয়েড-ওয়ার্শাল)

অল পেয়ার শর্টেস্ট পাথ অ্যালগরিদমকে ফ্লয়েড-ওয়ার্শাল অ্যালগরিদমও বলা হয়, যা একটি দেয়া ওয়েটেড গ্রাফ থেকে সকল জোড়ার শর্টেস্ট পাথ বের করতে ব্যবহৃত হয়। এই অ্যালগরিদমের ফলাফল হিসেবে, একটি ম্যাট্রিক্স জেনারেট হবে, যা গ্রাফের যেকোনো নোড থেকে অন্য সব নোড পর্যন্ত মিনিমাম ডিস্ট্যান্স উপস্থাপন করবে।

প্রথমে আউটপুট ম্যাট্রিক্স দেওয়া কস্ট ম্যাট্রিক্সের সমান। তারপর আউটপুট ম্যাট্রিক্স সব ভার্টেক্স 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
    display the current cost matrix
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