গ্রাফপড়তে ৫ মিনিট লাগবে

ফ্লয়েড-ওয়ার্শল অ্যালগরিদম (Floyd-Warshall Algorithm)

সবার থেকে সবার কাছে যানয়ার সবচেয়ে ছোট রাস্তা — জাস্ট একটা ট্রিপল লুপের ম্যাজিক

time: O(V³)space: O(V²)

ডাইকস্ট্রা (Dijkstra) বা বেলম্যান-ফোর্ড (Bellman-Ford) একটা ফিক্সড শুরুর জায়গা থেকে বাকি সব জায়গায় যানয়ার সবচেয়ে ছোট রাস্তার খোঁজ দেয়। কিন্তু যদি আপনার এমন একটা ম্যাপ লাগে, যেখানে যেকোনো একটা শহর থেকে অন্যযেকোনো শহরে যানয়ার সবচেয়ে সস্তা বা ছোট রাস্তা জানা দরকার হয়? আপনি চাইলে প্রতিটা শহর থেকে একবার করে ডাইকস্ট্রা চালাতে পারেন — অথবা আপনি ফ্লয়েড-ওয়ার্শল (Floyd-Warshall) ব্যবহার করতে পারেন। এটা ডায়নামিক প্রোগ্রামিংয়ের (DP) খুব সুন্দর আর ছিমছাম একটা অ্যালগরিদম, যা এক দানেই সবার থেকে সবার শর্টেস্ট পাথ বের করে দেয়।

ফ্লয়েড-ওয়ার্শল নেগেটিভ বা মাইনাস ওজনের রাস্তাও হ্যান্ডেল করতে পারে (তবে নেগেটিভ সাইকেল বা চক্র থাকলে পারে না)। এটা ছোট কিন্তু খুব ঘিঞ্জি বা ঘন (dense) ম্যাপের জন্য একদম পারফেক্ট, যেখানে আপনার একটা কমপ্লিট ডিস্ট্যান্স ম্যাট্রিক্স (Distance matrix) বা টেবিল দরকার হয় — যে টেবিলে লেখা থাকবে কোন শহর থেকে কোন শহরে যানয়ার সবচেয়ে ছোট রাস্তার দূরত্ব ঠিক কত।

সেই জাদুকরী ডিপি (DP) রিকারেন্স

এর মূল লজিকটা হলো: প্রতিটা সম্ভাব্য মাঝখানের শহর (intermediate node) k-এর জন্য চেক করে দেখা যে, i থেকে j-তে যানয়ার সময় সরাসরি না গিয়ে যদি k-এর ওপর দিয়ে ঘুরে যানয়া হয়, তবে রাস্তাটা কি ছোট বা সস্তা হয়?

pseudocode

// শুরুতে টেবিল সাজানেন:
// dist[i][j] = সরাসরি রাস্তা থাকলে তার দূরত্ব, না থাকলে ইনফিনিটি (Infinity)
// dist[i][i] = 0 (নিজের থেকে নিজের দূরত্ব সবসময় 0)

for k from 0 to V-1:        // মাঝখানের শহর হিসেবে চেক করুন
  for i from 0 to V-1:      // শুরুর শহর
    for j from 0 to V-1:    // গন্তব্য শহর
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]  // হ্যাঁ, ঘুরে গেলে রাস্তা ছোট হয়!

সব বাইরের (k) লুপ ঘোরা শেষ হলে, এই dist[i][j] টেবিলের ভেতরে i থেকে j-তে যানয়ার (যেকোনো মাঝখানের শহর ঘুরে হলেও) একদম সবচেয়ে ফাইনাল শর্টেস্ট দূরত্বটা জমা হয়ে থাকবে।

◈ Watch Floyd-Warshall

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

৪টা শহরের একটা উদাহরণ

ধরুন শহরগুলো হলো: A, B, C, D। রাস্তাগুলো: A→B=3, B→C=2, A→C=10, C→D=1, B→D=8।

শুরুতে dist[A][D] = ∞ (কারণ সরাসরি কোনো রাস্তা নেই)। এরপর যখন B-কে মাঝখানের শহর হিসেবে চেক করা হলো: dist[A][B] + dist[B][D] = 3+8 = 11 — দূরত্ব কমে ১১ হলো। এরপর যখন C-কে চেক করা হলো: dist[A][C] + dist[C][D] = 5+1 = 6 (কারণ A→B→C এর দূরত্ব ৫) — দূরত্ব কমে আরো ছোট, ৬ হয়ে গেলো। তাই A থেকে D-তে যানয়ার সবচেয়ে ছোট রাস্তা হলো ৬, যেটা A→B→C→D হয়ে যায়।

নেগেটিভ সাইকেল (Negative cycle) বা গোলকধাঁধা ধরা

অ্যালগরিদম চালানো শেষ হওয়ার পর টেবিলের কোনাকুনি (diagonal) দাগ বা ডায়াগোনাল চেক করুন। dist[i][i] সবসময় ০ হতে হবে (কারণ নিজের থেকে নিজের দূরত্ব ০)। কিন্তু যদি দেখেন কোনো dist[i][i] < 0 হয়ে গেছে, তার মানে ওই i নম্বর শহরের ভেতর দিয়ে এমন একটা নেগেটিভ সাইকেল যাচ্ছে যেটা দিয়ে বারবার ঘুরলে অসীম বা ইনফিনিট লাভ হয় — তাই আসল শর্টেস্ট পাথ আর বের করা সম্ভব না।

কখন ফ্লয়েড-ওয়ার্শল ব্যবহার করবেন?

যখন V বা শহরের সংখ্যা ছোট (সর্বোচ্চ কয়েকশো শহর) — কারণ O(V³) স্পিডের কারণে কয়েক হাজার শহর হলে এটা অনেক স্লো হয়ে যায়।
যখন আপনার শুধু একটা নির্দিষ্ট শহর থেকে নয়, বরং সব জোড়া (all pairs) শহরের মধ্যে সবচেয়ে ছোট রাস্তা দরকার।
যখন ম্যাপের কোনো কোনো রাস্তার খরচ নেগেটিভ বা মাইনাস হতে পারে (তবে নেগেটিভ সাইকেল থাকলে হবে না)।

অনেক বিশাল বড় অথচ ফাঁকা (sparse) ম্যাপের ক্ষেত্রে, প্রতিটা শহর থেকে আলাদা আলাদা ডাইকস্ট্রা চালানোই বেশি ফাস্ট হয়: O(V³) এর বদলে তখন সময় লাগে O(V × (V+E) log V)।

দ্রষ্টব্য: এই তিন স্তরের বা ট্রিপল লুপ দেখে ভয়ংকর মনে হতে পারে, কিন্তু প্রতিটা লুপের কাজ একদম সোজা: সে শুধু জিজ্ঞেস করে, 'আমি কি i থেকে j-তে যানয়ার সময় সরাসরি না গিয়ে k-তে ব্রেক দিয়ে বা থেমে গেলে খরচ বাঁচাতে পারবো?' — আর এই প্রশ্নটাই সম্ভাব্য সব k, i, এবং j-এর জন্য বারবার করা হয়।