মডিউল ৭_৭ঃ Floyd Warshall Algorithm

এখন আমরা দেখব Floyd Warshall এলগোরিদম কিভাবে কাজ করে।

নিচের গ্রাফটা খেয়াল করোঃ

Floyd warshall এলগোরিদমে আমরা এডজেসেন্সি ম্যাট্রিক্স এর মাধ্যমে করে থাকি।

এই গ্রাফের এডজেসেন্সি ম্যাট্রিক্স নিম্নরুপঃ

Floyd Warshall এলগোরিদমে আমরা একটা সিম্পেল স্টেপ মনে রাখবো আর সেটা হচ্ছে প্রতি দুইটি নোড এর মাঝে একটা মধ্যস্তথাকারী নোড আনবো এবং এরপর চেক করব যে সেই নোড এর মাধ্যমে সোর্স থেকে ডেস্টিনেশনে গেলে পাথ রিল্যাক্স হয় কিনা।

মধ্যস্ততাকারী নোড হিসেবে বোঝায় ধরি, ০ -> ১ এ যেতে ১২ কস্ট প্রয়োজন হয়। এখন ০ আর ১ মাঝে ধর একটা নোড আনলাম ২। ধরি ০->২ এ যেতে কস্ট ৩ আর ২->১ এ যেতে কস্ট ৪। তাহলে আমরা যদি ০ থেকে ২ হয়ে ১ এ যায় তাহলে আমাদের কস্ট লাগবে ৩+৪ = ৭ যা ১২ থেকে ভালো। তাই ০->১ এ যাওয়ার শর্টেস্ট ডিস্টেন্স আপডেট হয়ে হবে ৭।

উদাহরণ হিসেবে যদি দেখি,

এবার ০ কে মধ্যস্তথাকারী নোড হিসেবে আনিঃ

0->0->0 = 0

0->0->1 = 3

0->0->2 = infinte

0->0->3 = infinite

1->0->0 = infinite

1->0->1 = 0

1->0->2 = 4

1->0->3 = infinite

2->0->0 = infinite

2->0->1 = infinite

2->0->2 = 0

2->0->3 = 5

3->0->0 = infinite

3->0->1 = 7

3->0->2 = infinite

3->0->3 = 0

এবার ১ কে মধ্যস্তথাকারী নোড হিসেবে আনিঃ

0->1->0 = 0

0->1->1 = 3

0->1->2 =7[এখানে 0->1 = 3 এবং 1->2 = 4| 3+4 = 7<infinite তাই 0->2 আপডেট হয়ে হবে 7]

0->1->3 = infinite

1->1->0 = infinite

1->1->1 = 0

1->1->2 = 4

1->1->3 = infinite

2->1->0 = infinite

2->1->1 = infinite

2->1->2 = 0

2->1->3 = 5

3->1->0 = infinite

3->1->1 = 7

3->1->2 = 11[এখানে 3->1 = 7 এবং 1->2 = 4 | 7+4 = 11<infinite তাই 3->2 আপডেট হয়ে হবে 11]

3->1->3 = 0

এবার ২ কে মধ্যস্তথাকারী নোড হিসেবে আনিঃ

0->2->0 = 0

0->2->1 = 3

0->2->2 =7

0->2->3 = 12 [এখানে 0->2 = 7 এবং 2->3 = 5 | 7+5 = 12<infinite তাই 0->3 আপডেট হয়ে হবে 12]

1->2->0 = infinite

1->2->1 = 0

1->2->2 = 4

1->2->3 = 9 [এখানে 1->2 = 4 এবং 2->3 = 5 | 4+5 = 9<infinite তাই 1->3 আপডেট হয়ে হবে 9]

2->2->0 = infinite

2->2->1 = infinite

2->2->2 = 0

2->2->3 = 5

3->2->0 = infinite

3->2->1 = 7

3->2->2 = 11

3->2->3 = 0

এবার ৩ কে মধ্যস্তথাকারী নোড হিসেবে আনিঃ

0->3->0 = 0

0->3->1 = 3

0->3->2 =7

0->3->3 = 12

1->3->0 = infinite

1->3->1 = 0

1->3->2 = 4

1->3->3 = 9

2->3->0 = infinite

2->3->1 = 12 [এখানে 2->3 = 5 এবং 3->1 = 7| 5+7 = 12<infinite তাই 2->1 আপডেট হয়ে হবে 12]

2->3->2 = 0

2->3->3 = 5

3->3->0 = infinite

3->3->1 = 7

3->3->2 = 11

3->3->3 = 0

এর মাধ্যমেই আমাদের Floyd Warshall Algorithm শেষ হয়। এবং ফাইনাল ডিস্টেন্স এ্যারেতে আমরা সকল নোড থেকে সকল নোড এ যাওয়ার শর্টেস্ট ডিস্টেন্স পেয়ে যায়।