ডাইক্স্ট্রা এলগোরিদম: ইমপ্লিমেন্ট করতে গিয়ে যা যা শিখলাম!

 ডাইক্স্ট্রা এলগোরিদম: ইমপ্লিমেন্ট করতে গিয়ে যা যা শিখলাম 
১১ মে, ২০২১, মঙ্গলবার 

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

ডাইক্স্ট্রা এলগোরিদম (Dijkstra Algorithm) - এলগোরিদম কোর্সে খুবই কমন একটা টপিক। গ্রাফে একটা নোড থেকে বাকি সব নোডে যাওয়ার সবচেয়ে ছোট (বা শর্টেস্ট) পথ খুঁজে বের করাই এই এলগোরিদমের কাজ। এর কিছু সীমাবদ্ধতা আছে (যেমন, নেগেটিভ এজ সামলাতে পারে না) - এসব বাদ দিলে খুবই কার্যকরী একটা এলগোরিদম।  'লোভী পদ্ধতির' বা 'Greedy Strategy' এলগোরিদম বোঝার জন্যও ডাইক্স্ট্রা এলগোরিদম উদাহরণ হিসাবে শেখা উচিত। যদিও আমি নিচে ব্যাখ্যা করছি, তবুও আপনার জানা না থাকলে, কিংবা এই মুহুর্তে ডাইক্স্ট্রা এলগোরিদমটা মনে না থাকলে চট করে শাফায়াত আশরাফের বাংলা ব্লগ পড়ে নিতে পারেন। শাফায়াত আমাদের ডিপার্টমেন্টের জুনিয়র। ওর সাথে আমার কোনোদিন দেখা হয় নাই। কিন্তু ওর সাথে ওর এই ব্লগের কল্যানেই যোগাযোগ আছে। ওর গ্রাফের উপর বাংলা বইটাও খুবই চমৎকার। আমি ক্লাসের প্রিপারেশন নেয়ার জন্য ওর বইটা ব্যবহার করেছি। মায়ের ভাষায় কোনো কিছু পড়লে অনেক সহজবোধ্য হয়।  কিন্তু শাফায়াতের এলগোরিদম আর গ্রাফের উপর জ্ঞান আর লেখার হাত দুটো ভালো বলেই বইটা আরো ভালো হয়েছে।  

যাই হোক, খুব সংক্ষেপে ডাইক্স্ট্রা এলগোরিদম মূল আইডিয়াটা লেখার চেষ্টা করছি। Breadth First Search বা BFS হচ্ছে এর মূল ইঞ্জিন। BFS আবার কি? একটা গ্রাফের একটা নোড থেকে তার সবগুলো প্রতিবেশী নোডকে এক এক করে visit বা ঘুরে তারপর অন্য নোডে যাওয়াটাই BFS। নতুন কোনো নোডে যাওয়া মাত্রই তাকে একটা চিহ্ন বা দাগ দিয়ে দিতে হয় (রং gray বা ছাই করে দিয়ে), যাতে পরবর্তীতে আর ভিসিট করা না লাগে। আর একটা নোডের সবগুলো প্রতিবেশী নোড দেখা শেষ হয়ে গেলে আরেকটা চিহ্ন (রং কালো করে দিয়ে) 'complete' করে দিতে হয়।  আর এই পুরা কাজটা একটা কিউ (Queue) ডাটা স্ট্রাকচার দিয়ে ইমপ্লিমেন্ট করা হয়।  নিচে কোরমানের বইয়ের আলগোরিদমের ছবি দিয়ে দিচ্ছি (এইখানে d হচ্ছে মূল বা সোর্স নোড থেকে দূরত্ব/ধাপ আর 'পাই' আগের নোডের হিসাব রাখে):

      

ছবি ১: কোরমানের বই থেকে নেয়া [১]: BFS এলগোরিদম 

প্রথম যেটা খেয়াল করতে হবে, BFS এলগোরিদমে গ্রাফের প্রতিবেশী নোডগুলোর মধ্যে দূরত্ব ধরা হয় ১, অর্থাৎ এজের weight বা দূরত্ব সমান। এলগোরিদম রান করা শেষে একটা নোড থেকে বাকি নোড গুলো কত 'ধাপ' দূরে আর প্রতি নোডে যেতে কোন পথে যেতে হবে সেটা বের হয়।  কিন্তু ডাইক্স্ট্রা এলগোরিদম-এ গ্রাফের প্রতিটা নোডের সাথে তার প্রতিবেশী নোড শুধু সংযুক্তই না, ভিন্ন weight বা দূরত্বও দেয়া থাকে। সবচেয়ে কম দূরত্বে (বা Shortest Path) কিভাবে যাওয়া যায় সেটাই এই এলগোরিদম বের করে।  

উপরের এলগোরিদমে লাইন ১৩-র মতো 'একটা নোড ইতিমধ্যেই দেখা বা visit করা শেষ (রং সাদা না), তাই আর ঘাঁটানোর দরকার নাই '  - এই আইডিয়া বাদ দিয়ে ডাইক্স্ট্রা এলগোরিদম আরেকটু কৌতুহলী হয়। একটা নোডে যদি আরো কম খরচে (দরকার হলে অন্য আরেকটা নোড ঘুরে, কম দূরত্বে) পৌঁছানো যায়, তখন সেইটাই ভালো পথ - মূলত এই আইডিয়াটাই ডাইক্স্ট্রা এলগোরিদম। এই আপডেটটা নিচের 'Relax' মেথডটা করে থাকে:

ছবি ২: কোরমানের বই থেকে নেয়া[১]: সোর্স থেকে কোনো নোডের দূরত্ব (v.d) যদি অন্য আরেকটা নোড (u) ঘুরে কম দূরত্বে পৌঁছানো যায়, তাহলে সেইটাই ভালো পথ। w(u, v) নোড দুটোর দূরত্ব দেয়।  

আরেকটা কাজ ডাইক্স্ট্রা এলগোরিদম করে থাকে, সাধারণ কিউ (regular queue) ব্যবহার না করে প্রায়োরিটি কিউ ব্যবহার করে। কারণ যেহেতু আমরা শর্টেস্ট বা সবচেয়ে কম দূরত্বে পৌঁছাতে চাই, তাই সোর্স নোড থেকে কম দূরত্বের ভিত্তিতে একটা প্রায়োরিটি কিউ বা মিন-হিপ ব্যবহার করে কাজ করলে একই নোড বার বার ভিসিট বা ঘুরে দেখতে হয় না। আরেকটু বুঝিয়ে বলি: নিজের নোডে পৌঁছাতে যেহেতু কোনো দূরত্ব যাওয়া লাগে না, তাই শুরুতে সোর্স নোডের দূরত্ব শূন্য করে দিয়ে বাকি সব গুলো নোডের দূরত্ব অসীম করে দিয়ে প্রায়োরিটি কিউ বা মিন-হিপ তৈরী করা হয়।  এখন প্রায়োরিটি কিউ তে যতক্ষণ নোড আছে, প্রতিবার সবচেয়ে কম দূরত্বে পৌঁছানো যায় এমন নোড বের করে নিয়ে (Extract-Min ) (শুরুতে সোর্স নোড নিজেই থাকবে) সবগুলো প্রতিবেশীকে 'Relax' করিয়ে নিলেই হলো - সব সময় কম দূরত্বের নোডই অগ্রাধিকার পাবে, আর তা একবারই পাবে। আর এভাবে 'লোভী' হয়ে সব সময় কম দূরত্বের নোডকে নিয়ে চলতে থাকলে একসময় সব গুলো নোডে পৌঁছানোর শর্টেস্ট বা সবচেয়ে কমদূরত্বের পথ বের করে ফেলা যাবে। ব্যস, এইটাই ডাইক্স্ট্রা এলগোরিদম। নিচে এলগোরিদমটা দিয়ে দিচ্ছি:

ছবি ৩: কোরমানের বই থেকে নেয়া[১]: প্রায়োরিটি কিউ (বা মিন-হিপ) আর relax ফাঙ্কশন ব্যবহার করে ডাইক্স্ট্রা এলগোরিদম  

যাই হোক, আশা করি আপনি এখন পর্যন্ত সাথেই আছেন আর এই লাইনটা পড়ছেন। এইবার বলি এলগোরিদম ইমপ্লিমেন্ট করতে ঝামেলাটা কোথায় হলো। প্রথম সমস্যা হচ্ছে, কোডে গ্রাফ তৈরি করাটা একটু কঠিন। বেশ অনেকখানি সাপোর্টিং কোড লিখে তারপর ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্ট করতে হয়। একটু চিন্তা করে দেখুন, প্রতিটা নোডের প্রতিবেশী নোড গুলার লিস্ট রাখতে হবে,  সোর্স নোড থেকে দূরত্ব রাখতে হবে, সোর্স থেকে পথ বের করার জন্য আগের নোড কে সেটা রাখতে হবে ইত্যাদি।  নিচের কোড একটা নোড ক্লাস তৈরি করে:

ছবি ৪: নোড অথবা ভারটেক্স ক্লাস 

এবার যেহেতু প্রতিটা এজের weight  বা দূরত্ব হিসাবে নিতে হবে, তার জন্য একটা টেবিল তৈরী করতে হবে।  ধরা যাক, আমরা নোড u  আর v - এর মধ্যে এজ, u - v  এজের জন্য 'uv' স্ট্রিং কী (Key) আর weight বা দূরত্ব ইন্টিজার (Value)  হিসাবে হ্যাশ ম্যাপ -এ রাখলাম।  নিচের কোড গ্রাফের নোড গুলো কে একটা ArrayList -এ রাখবে, কিছু সাপোর্টিং ফাঙ্কশন থাকবে যেগুলো দিয়ে নোড গুলোর মধ্যে এজ আর weight যোগ করা যায়।  বলে রাখা ভালো, নোড গুলোকে নাম্বার দিয়ে নাম দিয়ে রাখছি, অর্থাৎ 'u', 'v' ইত্যাদি না বলে 1, 2 ইত্যাদি হিসাবে রাখছি।   

ছবি ৫: গ্রাফ ইমপ্লিমেন্টেশন

এবার গ্রাফ তৈরি করার জন্য সব কোড রেডি। যতগুলো নোডের গ্রাফ তৈরী করতে চাই, ধরা যাক, ৫ নোডের গ্রাফ, তাহলে main মেথডে Graph(5) কল করে প্রথমে নোডগুলো তৈরী করে নিয়ে, তারপর ম্যানুয়ালি বা ধরে ধরে এজ আর এজের weight যোগ করে দেয়া যাবে।    

এবার আসি, ডাইক্স্ট্রা এলগোরিদম ইম্প্লিমেন্টেশনে। প্রথমে relax ফাঙ্কশন। ছবি ২ -এর এলগোরিদম নিচের কোডে ইমপ্লিমেন্ট করলাম। Relax করলে true আর নাইলে false রিটার্ন করবে। কেন? একটু পরে বুঝিয়ে বলছি।  

ছবি ৬: Graph ক্লাসের ভেতরে প্রাইভেট relax ফাঙ্কশন 

 

এরপর ছবি ৩-এর ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্ট করার জন্য আমাদের প্রায়োরিটি কিউ (মিন-হিপ) লাগবে। গুগলে একটু ঘাঁটাঘাঁটি করে পেলাম যে জাভাতে util লাইব্রেরিতে প্রায়োরিটি কিউ (মিন-হিপ) আগে থেকেই ইমপ্লিমেন্ট করা আছে। কিন্তু যেহেতু আমাদের সোর্স নোড থেকে অন্য নোডের দূরত্বের ভিত্তিতে প্রায়োরিটি কিউ বানাতে হবে, তাই এই ব্যাপারটা একটু বলে দিতে হবে। আর এই কাজটা একটা ক্লাস যেটা Comparator ইন্টারফেস ইমপ্লিমেন্ট করে সেটা লিখে করতে হয়। এর পর শুধু প্রায়োরিটি কিউ-এর প্যারামিটার হিসাবে সেই ক্লাস তা পাস্ করে দিলে হয়ে যায়।  নিচের কোড:

ছবি ৭: Graph ক্লাসের ভেতরে Comparator ইন্টারফেস ইমপ্লিমেন্ট করা inner ক্লাস 

এবার শেষমেষ ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্টেশনের পালা। ছবি ৩ -এর কোড ধরে কোডটা ইমপ্লিমেন্ট করে দিলাম। খেয়াল করবেন, প্রায়োরিটি কিউ প্যারামিটার হিসাবে আমাদের Comparator ক্লাস নিচ্ছে। 

ছবি ৮: Graph ক্লাসের ভেতরে ডাইক্স্ট্রা মেথড। 

ব্যস, হয়ে গেছে তাই না? টেস্ট করার জন্য কিছু কোড লিখে, একটা টেস্ট গ্রাফের উপর রান করলাম, ডিবাগ করে দেখলাম, সেটাও (সৌভাগ্য কিংবা দুর্ভাগ্য বশতঃ?) কাজ করলো! কিন্তু যেই না স্টুডেন্টদের কোড দিয়ে অন্য টেস্ট কেস রান করতে বললাম, এরর খাওয়া শুরু হলো।  কোড বার বার চেক করেও বের করতে পারছিলাম না কেন কাজ করছে না। কোড তো এলগোরিদম হিসাবে ঠিক ভাবেই ইমপ্লিমেন্ট করলাম। কি একটা বেইজ্জতির ব্যাপার! শেষমেষ না পেরে বললাম, আজকে থাক, আমি পরে কোড চেক করে বের করার চেষ্টা করবো কেন কাজ করছে না।  

ঐদিন ক্লাস শেষে বেশ কিছুক্ষন ডিবাগ করে, ডকুমেন্টস, StackOverflow ঘেঁটে পরে বাগটা ধরতে পারলাম। আপনারা একটু চেষ্টা করে দেখবেন নাকি ধরতে পারেন কিনা? 

যাই হোক, এতক্ষন ধরে আসলে কনটেক্সট দেয়ার চেষ্টা করলাম। এইবার মূল ব্যাপারটা বলি। বাগটা হচ্ছে প্রায়োরিটি কিউ ব্যবহার করায়। কোনো প্রায়োরিটি কিউ তার প্রপার্টি -- আমাদের ক্ষেত্রে সোর্স নোড থেকে সবচেয়ে কম দূরত্বে থাকা নোড রুটে (root) থাকবে - এই ব্যাপারটা মেইনটেইন করবে কেবল শুরুতে যখন প্রায়োরিটি কিউ তৈরী করা হয় আর যখন কোনো অপারেশন করা হয়, যেমন poll (extract) কিংবা add ইত্যাদি কল করার পর। 

আমরা যখন ছবি ৬ -এ, 'relax' মেথড কল করে নোডের ভেতরে 'distance' বা দূরত্ব আপডেট করে দিচ্ছি, তখন ধরে নিচ্ছিলাম যে প্রায়োরিটি কিউ নিজে থেকে আপডেট হয়ে, স্ট্রাকচার বা কাঠামো বদলে সবচেয়ে কম দূরত্বের নোড কে উপরে বা রুটে (root) নিয়ে আসবে। এটা সম্পূর্ণ ভুল ধারণা। প্রায়োরিটি কিউ -এর ডকুমেন্টেশনে কোথাও সেটা বলা নাই।  

তাহলে উপায়? StackOverflow ঘেঁটে সল্যুশন বের করলাম। যখন 'relax' মেথড নোডের distance আপডেট করে true রিটার্ন করবে তখন ম্যানুয়ালি প্রায়োরিটি কিউতে একটা অপারেশন চালিয়ে - যেমন poll করে রুট বের করে নিয়ে আবার সেই একই রুট নোড add করে দিয়ে আমাদের প্রপার্টি 'force update' করে নিতে হবে, তবেই কাজ হবে। নিচে পরিবর্তিত কোড, হাইলাইট করে দিচ্ছি :

    

ছবি ৯: বাগ ফিক্স করা পরিবর্তিত ডাইক্স্ট্রা এলগোরিদম ইমপ্লিমেন্টেশন 

এখন আশা করি বুঝতে পারছেন, ছবি ৬ - এ কেন relax মেথডে true/false রিটার্ন করা জরুরি ছিল। আমি ভাবছিলাম এই ছোট কিন্তু খুব জরুরি বিষয়টা কেন পরিস্কারভাবে বলা হলো না? পরে আরেকটু ভালো করে পড়ার পর পেলাম কোরমানের বইয়ে 'relax' -এর সাথে Decrease-Key ফাঙ্কশনের সম্পর্ক বলা আছে - যেটা কিনা প্রায়োরিটি কিউয়ের নোডের key (আমাদের ক্ষেত্রে distance-ই key) কমিয়ে দিয়ে কিউ আপডেট করে। 

ছবি ১০: কোরমানের বই থেকে নেয়া[১]। ঘুরিয়ে বলা হয়েছে যে relax পরোক্ষভাবে অন্য ফাঙ্কশন কল করে প্রায়োরিটি কিউয়ের প্রপার্টি মেইনটেইন করবে   

যাই হোক, ঝানু প্রোগ্রামাররা হয়তো শুরুতেই ব্যাপারটা ধরতে পেরেছেন। কিন্তু আমার মতো দুর্বল প্রোগ্রামাররা হয়তো কত ঘন্টা এই বাগের পেছনে সময় ব্যয় করেছেন কে জানে? দিন শেষে শিক্ষা: যখনই কোনো এলগোরিদম শিখবো, কোডে ইমপ্লিমেন্ট করে তবেই থামতে হবে; কোডে কোনো লাইব্রেরি ব্যবহার করলে তার ডকুমেন্টেশন ভালো করে পড়ে নিতে হবে, শুধু চট করে ফাঙ্কশন কল করে কোনো কিছু হয়ে যাবে  ধরে নেয়া ঠিক না; কোড বেশি বেশি টেস্ট করার কোনো বিকল্প নাই।  

সবাইকে ধন্যবাদ!

--ইশতিয়াক 

রেফারেন্স: 

[১] 'Introduction to Algorithms' by Thomas H. Cormen and others.