ফ্লয়েড ওয়ারশাল অ্যালগরিদম

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

প্রথমে, আউটপুট ম্যাট্রিক্স গ্রাফের প্রদত্ত খরচ ম্যাট্রিক্সের মতোই। এর পরে, আউটপুট ম্যাট্রিক্স মধ্যবর্তী শীর্ষবিন্দু হিসাবে k এর সাথে সমস্ত শীর্ষবিন্দু আপডেট করা হবে৷

এই অ্যালগরিদমের সময় জটিলতা হল O(V^3), যেখানে V হল গ্রাফে শীর্ষবিন্দুর সংখ্যা।

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

ইনপুট:গ্রাফের খরচ ম্যাট্রিক্স। 0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ∞ 6 2 0 1 4 2 ∞∞ 1 1 0 2 ∞ 4∞ ∞ 220 2 ∞ 4∞ 220 ∞ 2 0 1∞ ∞ ∞ 4 1 1 0আউটপুট:সমস্ত জোড়ার সংক্ষিপ্ত পথের ম্যাট্রিক্স। 0 3 4 5 6 7 73 0 2 1 3 4 44 2 0 1 3 2 35 1 1 0 2 32 327 327 4 2 3 2 0 17 4 3 3 1 1 0 

অ্যালগরিদম

floydWarshal(খরচ)

ইনপুট - প্রদত্ত গ্রাফের খরচ ম্যাট্রিক্স।

আউটপুট: যেকোন শীর্ষ থেকে যেকোনো শীর্ষবিন্দুর মধ্যে সংক্ষিপ্ততম পথের জন্য ম্যাট্রিক্স।

k এর জন্য শুরু করুন :=0 থেকে n, i এর জন্য করুন :=0 থেকে n, j এর জন্য করুন :=0 থেকে n, করুন যদি খরচ[i,k] + খরচ[k,j] <খরচ[i, j], তারপর খরচ[i,j] :=খরচ[i,k] + খরচ[k,j] সম্পন্ন হয়েছে বর্তমান খরচ ম্যাট্রিক্স প্রদর্শন করুন 
উদাহরণ
 
#include#include
#define NODE 7#define INF 999using namespace std;//গ্রাফিন্ট 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]; //(int i =0; i 
আউটপুট
 
ম্যাট্রিক্স:0 3 5 4 6 7 73 0 2 1 3 4 45 2 0 1 3 2 34 1 0 2 3 36 3 3 2 0 2 17 4 2 3 2 0 17 4 3 3 1 1 /প্রে>