গবলিনদের সাথে তো এই দুই পর্বে ভালই টেক্কা দিলাম। তারা দুই দুইটা গোল খেয়ে খুবই রেগে। তারা ছুড়ে দিল আরও কঠিন এক চ্যালেঞ্জ। এবার তোমাকে বলতে হবে এক ভল্ট থেকে অন্য যেকোনো ভল্টে যাওয়ার সর্বনিম্ন দুরত্ব কত। আরে এ আর এমন কী? সব ভল্টে গিয়ে ডায়াক্সট্রা করে দিয়ে আসবো! কিন্তু ডায়াক্সট্রার কমপ্লেক্সিটি O(E log V)। তাহলে n নোডে এই কাজ করতে গেলে তো আর এই জন্মে শেষ হবে না! চিন্তার কোনো কারণ নেই। এই জাদুকরী সমস্যার সমাধান নিয়েই আসছে আরও এক মানুষেরই আবিষ্কার, ফ্লয়েড ওয়ার্শাল, ফ্লয়েড ওয়ার্শাল, ফ্লয়েড ওয়ার্শাল!

এবার বেশী কথা না বলে আমাদের মূল সমস্যাতে ফিরে যাই। আমাদের n-টা নোড আছে, আর এই নোড গুলো কিছু Edge দিয়ে কানেক্টেড। প্রতিটা Edge-এর কিছু Cost আছে। আমরা এটাও জানি যে গ্রাফে কোনো Negative Cycle নেই। কারণ Negative Cycleথাকলে সর্বনিম্ন দূরত্ব বের করা যায় না। আমাদের এখন এই n-টি নোডের প্রতিটির জন্য বাকি সকল নোডে যাওয়ার সর্বনিম্ন দূরত্ব বের করতে হবে।


তো ভাল কথা, আগের দুইটার মত এটাও আমরা নিজে নিজে সমাধান করার চেষ্টা করি। ডায়াক্সট্রা শিখে আমরা মূলত দুইটা আইডিয়া ব্যবহার করছিলাম।

  • distance-গুলো একটা অ্যারেতে সেভ করে রাখবো।
  • যখনই কোনো এজ ব্যবহার করে দুরত্ব কমানো যায়, তখনই দুরত্ব কমিয়ে দিবো, যার নাম কি না পাথ রিলাক্সেশন।

আমরা এই সমস্যার সমাধানেও ঠিক এ দু’টি আইডিয়াই ব্যবহার করবো।

আমরা একটা 2D array distance[N][N] নিয়ে রাখবো। distance[i][j] বলতে বোঝাবে i থেকে j-তে যাওয়ার সর্বনিম্ন দুরত্ব। আর Path Relaxation জন্য আমরা যা করবো, তা হল যখনই দেখবো i-থেকে j-তে যাওয়ার বর্তমান যে পথ আছে, সেটাতে না গিয়ে i-থেকে k-তে গিয়ে, পরে k থেকে j-তে গেলে দুরত্ব কমে আসে, তখন আমরা পাথ আপডেট করে দিবো। এই একটা লাইন বুঝতে পারলেই আমাদের এলগরিদম শেখা শেষ, তাই এই লাইনটা কয়েকবার পড়ে বোঝার চেষ্টা কর।

আমি যা বলতে চাচ্ছি তা হল, ধরা যাক, আমার 10 নোডের একটা গ্রাফ আছে। এখান থেকে আমি জানি 1 থেকে 2 তে যাওয়ার (বর্তমান) দুরত্ব 10.

2 থেকে 7-এ যাওয়ার বর্তমান দুরত্ব 20.

1 থেকে 7-এ যাওয়ার বর্তমান দুরত্ব 70.

তার মানে,

  • distance[1][2] = 10
  • distance[1][7] = 70
  • distance[2][7] = 20

খেয়াল করে দেখো, 1 থেকে 7 এ যাওয়ার যে পথটা আমরা বর্তমানে ব্যবহার করছি, সেটা ব্যবহার না করে 1 থেকে 2-এ গিয়ে পরে আবার 2 থেকে 7-এ গেলে দুরত্ব কমে আসে। কারণ distance[1][2] + distance[2][7] < distance[1][7]. তার মানে আমি এখন আর আগের পথ ব্যবহার না করে নতুন খুজে পাওয়া পথটা ব্যবহার করবো। তাহলে, আমার নতুন দুরত্ব হবেঃ

 

  • distance[1][2] = 10
  • distance[1][7] = 30
  • distance[2][7] = 20

আমরা এ আইডিয়াটা ব্যবহার করেই মূল সমস্যাটা সমাধান করবো।

আমরা প্রথমে ঠিক করবো i থেকে j-তে যাওয়ার পথে আমরা আর কোনো নোড ব্যবহার করবো না। তার মানে i থেকে j-তে সরাসরি এজ থাকলেই শুধু আমরা সে পথে যাবো।

তাহলে, প্রথমে আমরা dis[i][j]-এর সব ভ্যালু ইনফিনিটি দিয়ে ইনিশিয়ালাইজ করে দিবো। এরপর সব i->j এজের জন্য আমরা dis[i][j]-কে আপডেট করে দিবো। যদি একাধিক এজ থাকে, তাহলে নিবো সবচেয়ে কম কস্টের এজকে।

আমাদের এপ্রোচ হবে এমনঃ প্রথম k সংখ্যক নোড ব্যবহার করে i থেকে j-তে যাওয়ার সর্বনিম্ন দুরত্ব কত?

তার মানে k-এর মান যদি ২ হয়, তাহলে আমরা i থেকে j-তে যেতে কেবল ০, ১, ২ এই তিনটা নোড ব্যবহার করতে পারবো (করতেই হবে এমন কোনো কথা নেই)।

আমরা কীভাবে নিশ্চিত করতে পারি যে, আমরা শুধুমাত্র প্রথম k-টা নোড ব্যবহার করছি? আমরা একটি লুপ চালাবো যেটা 1 থেকে n পর্যন্ত ইটারেট করবে। তাহলে আমরা k-th ইটারেশনে নিশ্চিতভাবে বলতে পারবো যে এখন পর্যন্ত শুধুমাত্র 1 থেকে k তম নোডের জন্যই দুরত্ব আপডেট হয়েছে। তার মানে আমাদের একটা 1 থেকে n লুপ চালাতে হবে, যার কাজ হল k-তম নোড কোনটা হবে তা ঠিক করে দেওয়া।

int dis[51][51];
vector <int> edge[51];
vector <int> cost[51];
#define INF 1000000000
void floyd_warshall (int n)  {
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            dis[i][j] = INF;

    for (int i=1; i<=n; i++) {
        for (int j=0; j<edge[i].size(); j++) {
            dis[i][edge[i][j]] = min(dis[i][edge[i][]j], cost[i][j]);
        }
    }
    for (int k=1; k<=n; k++) {

    }
}

এখানে k কাজ করে অন্তর্বর্তী নোড হিসেবে। আমরা এই লুপের ভেতরে সকল সম্ভাব্য {i, j} পেয়ারের জন্য i থেকে k-তে গিয়ে আবার k থেকে j-তে গিয়ে দেখবো দুরত্ব কমে কিনা। তাহলে বাকি অংশ লিখে ফেলা যাক।

int dis[51][51];
vector <int> edge[51];
vector <int> cost[51];
#define INF 1000000000
void floyd_warshall (int n)  {
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            dis[i][j] = INF;

    for (int i=1; i<=n; i++) {
        for (int j=0; j<edge[i].size(); j++) {
            dis[i][edge[i][j]] = min(dis[i][edge[i][]j], cost[i][j]);
        }
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

– ব্যাস কাজ শেষ!

– ওই মিয়া! ফাইজলামি পাইছেন? এতটুকু কোডে এত কঠিন কাজ হয়ে গেছে?

– হ্যা ভাই, আসলেই কাজ শেষ। ছোট কোডের কাজ বেশী হয়, জানেন না? 😛

– আচ্ছা, k ভেতরে লিখে বাইরে i, j লিখলে সুন্দর হবে। এইভাবে লিখি?

– না! 😀 ওভাবে লিখলে গ্রিনগটসের ড্রাগন জেগে উঠবে।

এখানে k-এর কাজ হল প্রথম কয়টা নোড ব্যবহার করা হচ্ছে এই ব্যাপারটা নিশ্চিত করা। তাই এই কাজ ভেতরে করলে হবে না। ঠিক এই অর্ডারেই লুপগুলো লিখতে হবে।

আমরা এখানে গ্রাফ স্টোর করার জন্য Adjacency List ব্যবহার করেছিলাম। কিন্তু আমরা যদি Adjacency Matrix ব্যবহার করতাম, তাহলে আমাদের কাজ আরও অনেক সহজ হয়ে যেত! এমন একটা কোড চাইলে দেখতে পারো এই লিংকে

ফ্লয়েড ওয়ার্শাল এলগরিদমের ভিজ্যুয়ালাইজেশন

পুরো ব্যাপারটা খুব ভাল মত বোঝা হয়ে যাবে, যদি আমরা নিচের গ্রাফের জন্য ফ্লয়েড ওয়ার্শাল হাতে করে করে দেখি।

বল তো এই গ্রাফে k-এর কয়টা ইটারেশন লাগবে? যেহেতু n=7, k ইটারেট করবে 1 থেকে 7 পর্যন্ত।

এটা একবার হাতে করে নিলে ফ্লয়েড ওয়ার্শাল এলগরিদমের ধারণা একেবারে বুঝে যাবে। তবুও অলস লাগলে এই লিংকে গিয়ে দেখতে পারো।

ফ্লয়েড ওয়ার্শাল আসলেই কাজ করে? প্রমাণ কী?

আমরা ফ্লয়েড ওয়ার্শাল আরোহী (ইনডাকশন) পদ্ধতিতে প্রমাণ করার চেষ্টা করবো।

  • একদম শুরুতে ইনিশিয়ালাইজেশনের পর আমরা নিশ্চিতভাবে বলতে পারি, এতদূর পর্যন্ত সব ঠিক আছে। কারণ, এর মানে হল আমরা অন্তর্বর্তী কোনো নোড ব্যবহার না করেই (i, j)-এর সর্বনিম্ন দুরত্ব পেতে চাই।
  • এবার ধরা যাক k-1 ইটারেশন পর পর্যন্ত এলগরিদম ঠিকভাবে সর্বনিম্ন দুরত্ব বের করে দিয়েছে। তার মানে অন্তর্বর্তী নোড হিসেবে 1 থেকে k-1 পর্যন্ত নোডগুলো ব্যবহার করে সকল (i, j)-এর সর্বনিম্ন দুরত্ব আমাদের সঠিকভাবে বের করা আছে।
  • এখন k-তম ইটারেশনে দু’টি কেস হতে পারে। হয় i থেকে j-তে যাওয়ার জন্য আমাদের k-নোডটা ব্যবহার করলে দুরত্ব কমবে, নাহয় কমবে না। এখন dis[i][k]-তে (অন্তর্বর্তী নোড হিসেবে প্রথমে k-1 নোড ব্যবহার করে) i থেকে k-তে যাওয়ার সর্বনিম্ন দুরত্ব ঠিক মত হিসাব করা আছে। আবার dis[k][j]-তে (অন্তর্বর্তী নোড হিসেবে প্রথমে k-1 নোড ব্যবহার করে) k থেকে j-তে যাওয়ার সর্বনিম্ন দুরত্ব বের করা আছে। তার মানে আমরা নিশ্চিতভাবে বলতে পারি dis[i][k] + dis[k][j] ব্যবহার করলেই আমরা (অন্তর্বর্তী নোড হিসেবে) k-কে ব্যবহার করলে সর্বনিম্ন দুরত্ব কত হবে তা বের করতে পারবো।
  • তাহলে n-th ইটারেশন শেষে আমরা নিশ্চিতভাবে বলতে পারি যে, এখানে প্রথম n নোডকে অন্তর্বর্তী নোড হিসেবে ব্যবহার করে (অথবা না করে) সর্বনিম্ন দুরত্ব সঠিকভাবে নির্ণয় করা আছে। আর কোনো নোড বাকি নাই। তাই কাজ এখানেই শেষ!

অতএব, গাণিতিক আরোহ পদ্ধতিতে বলা যায় যে, … :p

 

 

Muntasir Wahed

Muntasir Wahed

System Administrator at স্বশিক্ষা.com
Jack of all trades, master of none.
Muntasir Wahed
Muntasir Wahed