মডিউল ৭_৬ঃ কেন Floyd Warshall এলগোরিদম প্রয়োজন?

আমরা সিঙ্গেল সোর্স শর্টেস্ট পাথ এলগোরিদম এর মধ্যে Bfs,Dijkstra,Bellmanford এই তিনটি এলগোরিদম শিখেছি।

এরা আমাকে একটি নিদিষ্ট সোর্স এর জন্য বাকি নোড গুলোর শর্টেস্ট পাথ বলে দিতে পারত। তবে যদি আমার এমন প্রয়োজন হয় যে যেকোনো নোড থেকে যেকোনো নোড এর শর্টেস্ট পাথ জানা প্রয়োজন তাহলে?

উপরের এলগোরিদম গুলো দিয়েও এই প্রবলেম সলভ করা যায়। তবে

BFS দিয়ে করলে টাইম কমপ্লেক্সিটি হবে O(V^3) এবং weighted গ্রাফে করা যাবে না।

Dijkstra দিয়ে করলে টাইম কমপ্লেক্সিটি হবে O(V^3logV) এবং নেগেটিভ সাইকেলে কাজ করে না|

Bellmanford দিয়ে করলে টাইম কমপ্লেক্সিটি হবে O(V^4)|

এই প্রবলেমকে এড়ানোর জন্য আমরা ব্যবহার করব Floyd Warshall Algorithm| এই এলগোরিদম এর মাধ্যমে O(V^3) কমপ্লেক্সিটিতে সকল ধরনের ওয়েটেড,নেগেটিভ,আনওয়েটেড গ্রাফে all pair shortest path বের করে দিতে পারে।