ফ্লয়েড-ওয়ারশাল অ্যালগরিদম (সর্বোচ্চ ছোট পথ)

ফ্লয়েড-ওয়ারশাল অ্যালগরিদম একটি প্রদত্ত ওজনযুক্ত গ্রাফ থেকে সকল জোড়ার সর্বনিম্ন পথ (all-pair shortest path) সমস্যা সমাধানের জন্য ব্যবহৃত হয়। এই অ্যালগরিদমের ফলাফল হিসেবে একটি ম্যাট্রিক্স তৈরি হয় যা গ্রাফের যেকোনো নোড থেকে অন্য যেকোনো নোড পর্যন্ত ন্যূনতম দূরত্ব প্রকাশ করে।

প্রথমে আউটপুট ম্যাট্রিক্স গ্রাফের দেওয়া কস্ট ম্যাট্রিক্সের সমান। এরপর সব ভেরটেক্স k কে ইন্টারমিডিয়েট ভেরটেক্স ধরে আউটপুট ম্যাট্রিক্স আপডেট করা হয়।

এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(V³), যেখানে V হল গ্রাফের ভেরটেক্স সংখ্যা।

ইনপুট এবং আউটপুট

ইনপুট: গ্রাফের কস্ট ম্যাট্রিক্স।
আউটপুট: সকল জোড়ার সর্বনিম্ন পথের ম্যাট্রিক্স।

অ্যালগরিদম

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

আউটপুট
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