গ্রাফ শর্টেস্ট পাথ: বেলম্যান ফোর্ড অ্যালগরিদম
Graph Theory Shortest Path/Bellmen-Ford Algorithm Bangla Tutorial/Finding Negative Cycle in a graph
শর্টেস্ট পাথ (Shortest path) অ্যালগরিদম গুলো দিয়ে গ্রাফের দুটি নোডের মধ্যে ক্ষুদ্রতম পথের দৈর্ঘ্য বের করা যায়। বেলম্যান ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm; Aka Single source shortest path) একটি অ্যালগরিদম যা গ্রাফের কোন একটি নোড থেকে গ্রাফের সকল নোডের মধ্যে সংক্ষিপ্ততম দূরত্ব গুলো বের করতে পারে। আজকের লিখায় আমরা বেলম্যান ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm) নিয়ে দেখবো। গ্রাফ থিওরির (Graph theory) বেসিক নিয়ে না জানলে আমার এই লিখাটা পরতে পারেন। গ্রাফ বেসিক: গ্রাফ এবং গ্রাফ এর রিপ্রেজেন্টেশন।
Bellman Ford Algorithm Bangla Tutorial
ধরা যাক আমাদের একটি সমস্যা সমাধান করতে হবে যাতে আমাদেরকে একটি গ্রাফ দেয়া থাকবে এবং একটি সোর্স নোড দেয়া থাকবে। আমাদেরকে ওই নোড থেকে গ্রাফের বাকি সকল নোডের মধ্যে ক্ষুদ্রতম দূরত্ব বের করতে হবে। এখানে আমাদের গ্রাফের মধ্যে নেগেটিভ সাইকেল/চক্র (Negative Cycle) থাকতে পারে, এবং এজ (Edge) গুলোর weight নেগেটিভ হতে পারে।
এই ধরনের সমস্যা সমাধানের জন্য বেলম্যান ফর্ড অ্যালগরিদম (Bellman Ford Algorithm) ব্যাবহার করা যাবে। এই অ্যালগরিদম সকল ধরনের গ্রাফেই কাজ করতে পারে। Bellman Ford অ্যালগরিদম গ্রাফে কোন নেগেটিভ সাইকেল থাকলেউ তা চিহ্নিত করতে পারে।
গ্রাফে নেগেটিভ সাইকেল কি? (What is negative cycle in a graph?)
গ্রাফে নেগেটিভ সাইকেল/চক্র হলো এমন একটি সাইকেল যার এজ গলোর যোগফল ঋণাত্মক হয়। নেগেটিভ সাইকেল থাকলে সোর্স থেকে ওই সাইকেলের কোনও নোডে যাওয়ার জন্য কোন শর্টেস্ট পথ নাই। কারণ ওই সাইকেলে ঘুরতে থাকলে মোট কস্ট (Cost) এর পরিমাণ আরও কমানো যাবে।
পাশের গ্রাফটিতে একটি ঋণাত্মক সাইকেল আছে, ধরতে পারছেন? সাইকেলটি হলো 2->3->4->2, মানে দুই থেকে চার নং নোডে গেলে আমাদের কস্ট দাড়ায় -4।
ঋণাত্মক সাইকেলে সমস্যা কি?
এখানে আমরা ধরে নিই, আমাদেরকে ১ নং নোড থেকে ৪ নং নোডে যেতে হবে। আমরা অনেক ঘুরাঘুরি করে, 1 -> 3 -> 2 -> 4 এ আসলাম, মোট কস্ট হলো ৮। কিন্তু এখানেই না থেমে আমাদের এলগরিদমের আরেক্টু শখ হলো ঘুরাঘুরি করার, তাই সে আবার 4 -> 3 -> 2 -> 4 এ আসলো। তো আবার ঘুরে ৪ এ আসতে তার খরচ হলো (কস্ট) পুর্বের এমা, কস্ট আরও কমে গেলো। আমাদের অ্যালগরিদম যদি আরও শখ করে দেখা যাবে প্রতিবারে এই সাইকেলের যেকোনো নোডে ঘুরাঘুরি করলেই কস্টের মান ৪ করে কমে যাবে। তাহলে কি বলা যায়? এই নোডের সর্বনিম্ন কস্ট আসলে ঋণাত্মক অসীম। এখানে খেয়াল করি যে গ্রাফে ঋণাত্মক সাইকেল থাকা মানে এই না যে আমরা ঋণাত্মক অসীম মানে পৌছাবো। অনেক সমস্যাই আছে যেখানে গ্রাফে ঋণাত্মক সাইকেল বের করতে বলে অথবা শুরুর নোড থেকে ঋণাত্মক সাইকেলের কোনও নোডে যেতে বলে। এমন ক্ষেত্রে আমরা বেলম্যান ফোর্ড ( Bellman Ford) অ্যালগরিদম ব্যাবহার করতে পারি।
বেলম্যান ফোর্ড(Bellman Ford) অ্যালগরিদম কিভাবে কাজ করে?
বেলম্যান ফোর্ড অ্যালগরিদম কিভাবে কাজ করে তা আমরা একটু ভিজুয়ালাইজ করবো। এর জন্য আমরা প্রথমে আমাদের নিচের গ্রাফটা দেখে নিই,
এখানে আমাদেরক একটা ডিরেক্টেড গ্রাফ দেয়া আছে। এখানে প্রতিটা এজের (Edge) এর উপরে তাদের কস্ট (Cost) দেয়া আছে। আমাদের এই গ্রাফে মোট ৬ টি নোড আছে এবং ৬ টি এজ আছে। আমরা লক্ষ করলে দেখবো আমাদের এই গ্রাফের ১,৩,৪, এবং ২ নোড মিলে -৩ কস্টের একটি নেগেটিভ সাইকেল গঠন করেছে। আমরা আমাদের এই গ্রাফটিকে এজলিস্ট ব্যাবহার করে উপস্থাপন করবো। আমাদের এই গ্রাফের জন্য এজলিস্টের গঠন হবে পাশে/নিচের মতো ।
এজলিস্টের প্রথমে থাকবে একটি নোড U এবং পরে আরেকটি নোড V থাকবে। তারপর U থেকে V তে যাউয়ার যে কস্ট বা weight তার মান W দেয়া থাকবে। আমরা উপরের গ্রাফ এবং পাশের লিস্ট থেকে দেখতে পাই,
- ০ থেকে ১ নং নোডে যাউয়ার কস্ট = ১০
- ১ থেকে ২ এ যাওয়ার কস্ট = ১
- ২ থেকে ৪ এ যাওয়ার কস্ট = ৩
- এভাবে ৪ থেকে ৩ এর কস্ট -১১, ৩ থেকে ১ এর কস্ট ৪ এবং ৪ থেকে ৫ এর কস্ট ২২।
বেলম্যান ফোর্ড অ্যালগরিদম কিভাবে কাজ করে?
Bellman Ford algorithm কে বুঝার জন্য আমরা প্রথম ছবির সাহায্যে ভিজুয়ালইজ করবো। পরে কোডে হাত দিবো।
ধাপ ১ঃ প্রথমে আমাদেরকে সোর্স নোড (শুরুর নোড) বাদে প্রত্যেকটি নোডের কস্ট অসীম করে দিতে হবে। যেহেতু আমরা জানি না শুরুর নোড থেকে কোনও নোডে যেতে সর্বনিম্ন কি পরিমাণ কস্ট লাগবে। কিন্তু আমরা শুরুর নোডের কস্ট শূন্য করে দিতে পারি। কারন শুরুর নোড থেকে আমাদের কোন নোডেই যেতে হয় না।
ধাপ ২ঃ এরপর আমরা আমাদের এজলিস্টের শুরু থেকে ধরে ধরে গ্রাফে আগানো শুরু করবে। এজলিস্টের প্রথমেই ০ থেকে ১ নং নোডে যাওয়া হয়েছে, যেখানে এজ এর weight হলো ১০। আমরা এই রুল মেনে প্রত্যেকটা V নোডের কস্ট আপডেট করবো। এখানে আমাদের U=০ নং নোড, V=১ নং নোড, এবং তাদের Weight = ১০। তাই আমাদের ১ নং নোডের কস্ট হবে । এখানে আমাদের ১ নং নোডের কস্ট অসীম থেকে ১০ এ আপডেট হবে। একই ভাবে আমরা ১ থেকে ২ এ যাওয়ার সময় ২ নং নোডের মান এভাবে আপডেট করবো। । এখানে আমাদের cost[u]=cost[1]=10, আমরা আগের বার পেয়েছিলাম। এভাবে আমরা ২ থেকে ৪ এবং ৪ থেকে ৩ এ গিয়েছি। এখন ৩ থেকে ৪ এ যাওয়ার জন্য আমাদের আগের রুল ই মানতে হবে। এখানে U=৩ নং নোড এবং V=১ নং নোড। সুতরাং আমাদের এ এর জন্য নতুন কস্ট হবে, । এরপর আমরা একই ভাবে ৪ থেকে ৫ ভিজিট করবো। এই ধাপ শেষে আমাদের আউটপুট গ্রাফ হবে এরকম,
ধাপ ৩ঃ উপরের ১ নং প্রসেস আরও N-2 বার রিপিট করবো। যেখানে N হলো মোট নোডের সংখ্যা। কেন? তার উত্তর হচ্ছে, গ্রাফে যদি N টি নোড থাকে তাহলে একটি নোড থেকে আরেকটি নোডে যেতে সর্বচ্চো N-1 টি নোড ব্যাবহার করতে হবে। তার মানে আমাদের গ্রাফের নোড গুলো সর্বচ্চো N-1 বার আপডেট হতে পারে। এখানে আমরা ২ নং ধাপে ১ টি সম্পন্ন করেছি, N-2 টা ধাপ বাকি রয়েছে।
আমরা যদি আমাদের গ্রাফের মধ্যে N-1 টি ধাপে আপডেট শেষ করি তাহলে আমাদের আউটপুট গ্রাফ নিচের মতো হওয়ার কথা।
এখানে ঋণাত্মক সাইকেলের নোড গুলোতে নেগেটিভ মান এসেছে দেখে ভয় পাওয়ার কিছু নেই। এদের জন্য সংজ্ঞায়িত কোন শর্টেস্ট পাথ নেই। আরও ঘুরলে আরও কমত এরকম অবস্থা। আমাদের গ্রাফে নেগেটিভ সাইকেল না থাকলে সব ঠিকই থাকত। তবে ঋণাত্মক সাইকেল দেখানোর জন্য আমি ইচ্ছা করেই এই গ্রাফ দিয়েছি। আপনারা চাইলে ৪ থেকে ৩ নং নোডের এজের মান -10 করে দেখতে পারেন। এতে করে আমরা ৫ ধাপ শেষে নিচের মতো আউটপুট পাবো।
আশা করি এতদূর পর্যন্ত বুঝা গেছে,। এখন আমরা সরাসরি কোডে ঝাপ দিবো। কোড বেশি কঠিন না। আমরা C/C++ এর struct ব্যবহার করবো এজলিস্ট বানাতে।
বেলম্যান ফোর্ড অ্যালগরিদম কোড করা
আমরা বেলম্যান ফোর্ড অ্যালগরিদম কোড করার সময় দুই ধাপে করবো। প্রথম ধাপে আমরা শর্টেস্ট পাথ বের করবো N-1 স্টেপে। আমরা কোডটি দেখি। কোডেই বাংলায় কমেন্ট করে রাখলাম, যাতে বুঝতে সুবিধে হয়।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
/* Sharif Hasan - CSE, PUST Apr 24, 2020 02: 14 PM */ #include<bits/stdc++.h> using namespace std; /*Main function*/ int main() { struct Edge{ int u,v,weight; }; Edge a,b,c,d,e,f; /*আমরা এজ লিস্ট তৈরি করছি, a,b,c,d,e,f যথা ক্রমে আমাদের বিভিন্ন এজ নির্দেশ করছে */ a.u=0;a.v=1;a.weight=10; b.u=1;b.v=2;b.weight=1; c.u=2;c.v=4;c.weight=3; d.u=4;d.v=3;d.weight=-11; e.u=3;e.v=1;e.weight=4; f.u=4;f.v=5;f.weight=22; vector <Edge> E={a,b,c,d,e,f}; /*একটা অ্যারে নিতে হবে Cost যার সাইজ হবে মোট নোডের সংখ্যা। নামে, যেখানে আমরা প্রতিটি আপডেটের হিসাব রাখবো। প্রাথমিক ভাবে আমরা শুরুর নোড ০ বাদে সব নোডের মান INT_MAX বা অসীম করে রাখবো */ int n=6; int cost[n]; for(int i=1;i<n;i++){ cost[i]=INT_MAX; } cost[0]=0; //শুরুর নোড এর মান শূন্য করে দিলাম for(int i=0;i<n-1/*n-1 বার চলবে*/;i++){ for(Edge edge:E){//প্রতিটা এজের মধ্যে ঘুরতে হবে if(cost[edge.v]>cost[edge.u]+edge.weight){//যদি নতুন কস্ট আগে রাখা কস্টের চেয়ে ছোট হয়, তবে cost[edge.v]=cost[edge.u]+edge.weight; //আমাদের পুরাতন কস্টকে নতুন কস্ট দ্বারা আপডেট করতে হবে। } } } //নেগেটিভ সাইকেল চেক করার কোড এখানে হবে //এখন আমরা আমাদের কস্ট অ্যারে টা প্রিন্ট করে দেখি কি খবর। for(int i=0;i<n;i++){ cout<<"Distance of node "<<i<<" from node 0 is "<<cost[i]<<endl; } return 0; } |
আশা করি কোডটি সহজেই বুঝবেন। না বুঝলে কমেন্ট বক্সে বা আমার ফেসবুকে/ মেইলে মেসেজ দিতে ভুলবেন না।
এখন আসি আমরা কিভাবে নেগেটিভ সাইকেল আছে নাকি চেক করবো। এর জন্য আমরা লুপটা আরেকবার ঘুরাবো। যদি তখন আপডেট সম্ভব হয় তার মানে নেগেটিভ সাইকেল আছে। এর জন্য আমরা প্রথম লুপের পরে মার্ক করা জায়গায় এই কোডটি লিখবো।
|
1 2 3 4 5 6 7 |
for(Edge edge:E){//প্রতিটা এজের মধ্যে ঘুরতে হবে if(cost[edge.v]>cost[edge.u]+edge.weight){//যদি নতুন কস্ট আগে রাখা কস্টের চেয়ে ছোট হয়, তবে //তারমানে আরও আপডেট হচ্ছে এবং আমাদের গ্রাফে নেগেটিভ সাইকেল আছে। cout<<"Negetive cycle detected\n"; break; } } |
বেলম্যান ফোর্ড অ্যালগরিদম এনালাইসিস, ( Bellman Ford algorithm analysis)
Time complexity: এই এলগরিদমের টাইম কমপ্লেক্সিটি এখানে আমাদের প্রধান লুপ চলছে N বার এবং নেস্টেড লুপ চলছে M=মোট এজের সংখ্যা, সংখ্যক বার। আমরা চাইলে এই এলগরিদমকে আরও অপ্টিমাইজ করতে পারি। এটা হলো আমরা যখন দেখবো নেস্টেড লুপের সময় কোনও বাহুতেই আপডেট হয় নি তখন লুপ ব্রেক করে ফেলব। কারণ এর পরে আর আপডেট হবে না।
এই অ্যালগরিদম কিভাবে কাজ করে এটা দেখার জন্য এই লিঙ্কটি দেখুন।
