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

$n$ টি ভার্টেক্স বিশিষ্ট একটি ডিরেক্টেড বা আনডিরেক্টেড ওয়েটেড গ্রাফ $G$ দেওয়া আছে। কাজ হলো প্রতিটি জোড়া ভার্টেক্স $i$ এবং $j$-এর মধ্যে শর্টেস্ট পাথের দৈর্ঘ্য $d_{ij}$ বের করা।

গ্রাফে নেগেটিভ ওয়েট এজ থাকতে পারে, তবে নেগেটিভ ওয়েট সাইকেল থাকতে পারবে না।

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

এই অ্যালগরিদমটি নেগেটিভ সাইকেলের উপস্থিতি শনাক্ত করতেও ব্যবহার করা যায়। অ্যালগরিদম শেষে কোনো ভার্টেক্স $v$ থেকে নিজের কাছে দূরত্ব নেগেটিভ হলে গ্রাফে নেগেটিভ সাইকেল আছে।

এই অ্যালগরিদমটি ১৯৬২ সালে রবার্ট ফ্লয়েড ও স্টিফেন ওয়ার্শালের প্রবন্ধে একই সাথে প্রকাশিত হয়েছিল। তবে ১৯৫৯ সালে বার্নার্ড রয় মূলত একই অ্যালগরিদম প্রকাশ করেছিলেন, কিন্তু তার প্রকাশনাটি অলক্ষিত থেকে যায়।

অ্যালগরিদমের বর্ণনা#

অ্যালগরিদমের মূল ধারণা হলো যেকোনো দুটি ভার্টেক্সের মধ্যে শর্টেস্ট পাথ খোঁজার প্রক্রিয়াকে কয়েকটি ক্রমবর্ধমান ধাপে ভাগ করা।

ভার্টেক্সগুলোকে ১ থেকে $n$ পর্যন্ত সংখ্যায়িত করি। দূরত্বের ম্যাট্রিক্স হলো $d[ ][ ]$।

$k$-তম ধাপের ($k = 1 \dots n$) আগে, যেকোনো ভার্টেক্স $i$ এবং $j$-এর জন্য $d[i][j]$ ভার্টেক্স $i$ এবং ভার্টেক্স $j$-এর মধ্যে শর্টেস্ট পাথের দৈর্ঘ্য সংরক্ষণ করে, যেখানে পাথে শুধুমাত্র $\{1, 2, ..., k-1\}$ ভার্টেক্সগুলো অভ্যন্তরীণ ভার্টেক্স হিসেবে থাকে।

অন্যভাবে বলতে গেলে, $k$-তম ধাপের আগে $d[i][j]$-এর মান ভার্টেক্স $i$ থেকে ভার্টেক্স $j$-তে শর্টেস্ট পাথের দৈর্ঘ্যের সমান, যদি এই পাথ শুধুমাত্র $k$-এর ছোট নম্বরের ভার্টেক্সে প্রবেশ করতে পারে (পাথের শুরু ও শেষ এই বৈশিষ্ট্য দ্বারা সীমাবদ্ধ নয়)।

এই বৈশিষ্ট্যটি প্রথম ধাপের জন্য ধারণ করে তা নিশ্চিত করা সহজ। $k = 0$-এর জন্য, আমরা ম্যাট্রিক্সটি পূরণ করতে পারি $d[i][j] = w_{i j}$ দিয়ে যদি $i$ এবং $j$-এর মধ্যে $w_{i j}$ ওয়েটের একটি এজ থাকে এবং $d[i][j] = \infty$ দিয়ে যদি কোনো এজ না থাকে। বাস্তবে $\infty$ হবে কোনো বড় মান। আমরা পরে দেখব, এটি অ্যালগরিদমের একটি শর্ত।

ধরুন এখন আমরা $k$-তম ধাপে আছি, এবং আমরা ম্যাট্রিক্স $d[ ][ ]$ এমনভাবে গণনা করতে চাই যা $(k + 1)$-তম ধাপের শর্তপূরণ করে। আমাদের কিছু ভার্টেক্স জোড়া $(i, j)$-এর জন্য দূরত্ব ঠিক করতে হবে। মৌলিকভাবে দুটি ভিন্ন ক্ষেত্র আছে:

  • $\{1, 2, \dots, k\}$ সেটের অভ্যন্তরীণ ভার্টেক্স সহ ভার্টেক্স $i$ থেকে ভার্টেক্স $j$-তে শর্টেস্ট পথ $\{1, 2, \dots, k-1\}$ সেটের অভ্যন্তরীণ ভার্টেক্স সহ শর্টেস্ট পাথের সাথে মিলে যায়।

    এক্ষেত্রে, রূপান্তরের সময় $d[i][j]$ পরিবর্তন হবে না।

  • $\{1, 2, \dots, k\}$ অভ্যন্তরীণ ভার্টেক্স সহ শর্টেস্ট পাথ আরও ছোট।

    এর মানে নতুন, ছোট পাথটি ভার্টেক্স $k$ দিয়ে যায়। এর মানে আমরা $i$ ও $j$-এর মধ্যে শর্টেস্ট পাথকে দুটি পাথে ভাগ করতে পারি: $i$ ও $k$-এর মধ্যে পাথ, এবং $k$ ও $j$-এর মধ্যে পাথ। এটি স্পষ্ট যে এই দুটি পাথই শুধুমাত্র $\{1, 2, \dots, k-1\}$-এর অভ্যন্তরীণ ভার্টেক্স ব্যবহার করে এবং সে অর্থে শর্টেস্ট পাথ। তাই আমরা ইতিমধ্যে সেই পাথগুলোর দৈর্ঘ্য আগেই গণনা করেছি, এবং $i$ ও $j$-এর মধ্যে শর্টেস্ট পাথের দৈর্ঘ্য $d[i][k] + d[k][j]$ হিসেবে গণনা করতে পারি।

এই দুটি ক্ষেত্র একত্রিত করে আমরা দেখি যে $k$-তম ধাপে সকল জোড়া $(i, j)$-এর দৈর্ঘ্য নিম্নলিখিতভাবে পুনর্গণনা করা যায়:

$$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

অতএব, $k$-তম ধাপে যা করতে হবে তা হলো সকল ভার্টেক্স জোড়ার উপর ইটারেট করা এবং তাদের মধ্যে শর্টেস্ট পাথের দৈর্ঘ্য পুনর্গণনা করা। ফলস্বরূপ, $n$-তম ধাপের পর, দূরত্ব ম্যাট্রিক্সে $d[i][j]$-এর মান $i$ ও $j$-এর মধ্যে শর্টেস্ট পাথের দৈর্ঘ্য, অথবা $\infty$ যদি ভার্টেক্স $i$ ও $j$-এর মধ্যে কোনো পাথ না থাকে।

একটি শেষ মন্তব্য — $k$-তম ধাপের শর্টেস্ট পাথগুলো সাময়িকভাবে সংরক্ষণের জন্য আমাদের আলাদা দূরত্ব ম্যাট্রিক্স $d_{\text{new}}[ ][ ]$ তৈরি করার দরকার নেই, অর্থাৎ যেকোনো ধাপে সরাসরি ম্যাট্রিক্স $d[ ][ ]$-এ সকল পরিবর্তন করা যায়। আসলে $k$-তম ধাপে আমরা সর্বাধিক দূরত্ব ম্যাট্রিক্সের যেকোনো পাথের দূরত্ব উন্নত করছি, তাই $(k+1)$-তম ধাপে বা পরে প্রক্রিয়াকরণ করা কোনো ভার্টেক্স জোড়ার শর্টেস্ট পাথের দৈর্ঘ্য খারাপ করতে পারি না।

এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি স্পষ্টতই $O(n^3)$।

ইমপ্লিমেন্টেশন#

ধরুন $d[][]$ একটি $n \times n$ আকারের ২D অ্যারে, যা পূর্বে ব্যাখ্যা করা ০-তম ধাপ অনুসারে পূরণ করা হয়েছে। এছাড়াও আমরা ০-তম ধাপে যেকোনো $i$-এর জন্য $d[i][i] = 0$ সেট করব।

তাহলে অ্যালগরিদমটি নিম্নরূপে ইমপ্লিমেন্ট করা হয়:

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

ধরে নেওয়া হচ্ছে যে যেকোনো দুটি ভার্টেক্স $i$ ও $j$-এর মধ্যে কোনো এজ না থাকলে, ম্যাট্রিক্সে $d[i][j]$-তে একটি বড় সংখ্যা আছে (এত বড় যে এই গ্রাফে যেকোনো পাথের দৈর্ঘ্যের চেয়ে বড়)। তাহলে এই এজ নেওয়া সর্বদা অলাভজনক হবে, এবং অ্যালগরিদম সঠিকভাবে কাজ করবে।

তবে গ্রাফে নেগেটিভ ওয়েট এজ থাকলে, বিশেষ ব্যবস্থা নিতে হবে। অন্যথায় ম্যাট্রিক্সের ফলাফল মানগুলো $\infty - 1$, $\infty - 2$ ইত্যাদি আকারের হতে পারে, যা অবশ্যই নির্দেশ করে যে সংশ্লিষ্ট ভার্টেক্সগুলোর মধ্যে কোনো পাথ নেই। তাই গ্রাফে নেগেটিভ ওয়েট এজ থাকলে, ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম নিম্নলিখিতভাবে লেখা ভালো, যাতে অস্তিত্বহীন পাথ ব্যবহার করে ট্রানজিশন না করে।

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

শর্টেস্ট পাথে ভার্টেক্সের ক্রম পুনরুদ্ধার#

অতিরিক্ত তথ্য সংরক্ষণ করা সহজ যার মাধ্যমে যেকোনো দুটি প্রদত্ত ভার্টেক্সের মধ্যে শর্টেস্ট পাথ ভার্টেক্সের ক্রম আকারে পুনরুদ্ধার করা যাবে।

এর জন্য, দূরত্ব ম্যাট্রিক্স $d[ ][ ]$-এর পাশাপাশি, পূর্বসূরীদের একটি ম্যাট্রিক্স $p[ ][ ]$ সংরক্ষণ করতে হবে, যেটিতে দুটি ভার্টেক্সের মধ্যে শর্টেস্ট দূরত্ব সর্বশেষ কোন ধাপে পরিবর্তিত হয়েছে তার নম্বর থাকবে। এটি স্পষ্ট যে ধাপের নম্বরটি কাঙ্ক্ষিত শর্টেস্ট পাথের মাঝখানের একটি ভার্টেক্স ছাড়া আর কিছু নয়। এখন শুধু ভার্টেক্স $i$ ও $p[i][j]$, এবং $p[i][j]$ ও $j$-এর মধ্যে শর্টেস্ট পাথ খুঁজতে হবে। এটি শর্টেস্ট পাথের একটি সরল রিকার্সিভ পুনর্গঠন অ্যালগরিদমের দিকে নিয়ে যায়।

বাস্তব ওয়েটের ক্ষেত্র#

যদি এজের ওয়েটগুলো পূর্ণ সংখ্যা না হয়ে বাস্তব হয়, তাহলে ফ্লোট টাইপ নিয়ে কাজ করার সময় যে ত্রুটি ঘটে তা হিসাবে নিতে হবে।

ফ্লয়েড-ওয়ার্শাল অ্যালগরিদমে ত্রুটি খুব দ্রুত জমা হওয়ার অপ্রীতিকর প্রভাব আছে। আসলে প্রথম ধাপে $\delta$ ত্রুটি থাকলে, এই ত্রুটি দ্বিতীয় ইটারেশনে $2 \delta$, তৃতীয় ইটারেশনে $4 \delta$ হিসেবে ছড়িয়ে পড়তে পারে, ইত্যাদি।

এটি এড়াতে নিম্নলিখিত তুলনা ব্যবহার করে ত্রুটি (EPS = $\delta$) হিসাবে নিতে অ্যালগরিদম পরিবর্তন করা যায়:

if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j];

নেগেটিভ সাইকেলের ক্ষেত্র#

আনুষ্ঠানিকভাবে ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম নেগেটিভ ওয়েট সাইকেল ধারণকারী গ্রাফে প্রযোজ্য নয়। তবে সকল ভার্টেক্স জোড়া $i$ ও $j$-এর জন্য যেখানে $i$ থেকে শুরু হয়ে একটি নেগেটিভ সাইকেল পরিদর্শন করে $j$-তে শেষ হওয়ার মতো কোনো পাথ নেই, অ্যালগরিদম এখনও সঠিকভাবে কাজ করবে।

যে ভার্টেক্স জোড়ার জন্য উত্তর নেই (তাদের মধ্যে পাথে নেগেটিভ সাইকেলের উপস্থিতির কারণে), ফ্লয়েড অ্যালগরিদম দূরত্ব ম্যাট্রিক্সে যেকোনো সংখ্যা (সম্ভবত অত্যন্ত নেগেটিভ, কিন্তু অগত্যা নয়) সংরক্ষণ করবে। তবে ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম উন্নত করা সম্ভব, যাতে এটি এরকম ভার্টেক্স জোড়াগুলো সাবধানে সামলায় এবং আউটপুট দেয়, যেমন $-\text{INF}$।

এটি নিম্নলিখিতভাবে করা যায়: প্রদত্ত গ্রাফের জন্য স্বাভাবিক ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম চালাই। তাহলে ভার্টেক্স $i$ ও $j$-এর মধ্যে শর্টেস্ট পাথ নেই যদি এবং কেবল যদি, এমন একটি ভার্টেক্স $t$ থাকে যেন $t$, $i$ থেকে পৌঁছানোযোগ্য এবং $j$, $t$ থেকে পৌঁছানোযোগ্য, যেখানে $d[t][t] < 0$।

এছাড়াও, নেগেটিভ সাইকেল সহ গ্রাফে ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম ব্যবহার করার সময় মনে রাখতে হবে যে দূরত্ব দ্রুত তাৎপর্যপূর্ণভাবে (exponentially) নেগেটিভে যেতে পারে। তাই কোনো মান (যেমন $-\text{INF}$) দ্বারা ন্যূনতম দূরত্ব সীমিত করে ইন্টিজার ওভারফ্লো সামলাতে হবে।

গ্রাফে নেগেটিভ সাইকেল খোঁজার বিষয়ে আরও জানতে, পৃথক নিবন্ধ গ্রাফে নেগেটিভ সাইকেল খোঁজা দেখুন।

অনুশীলন সমস্যা#