এই ব্লগ পোস্টে আমরা ডাইকস্ট্রার অ্যালগরিদমের মূলনীতি, উদাহরণ এবং বাস্তব প্রয়োগগুলো সহজবোধ্যভাবে ব্যাখ্যা করব।

ভূমিকা

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

গ্রাফ এবং মৌলিক ধারণা

ডাইকস্ট্রার অ্যালগরিদম বুঝতে হলে, কম্পিউটার বিজ্ঞানের প্রেক্ষাপটে “গ্রাফ” বলতে কী বোঝায়, তা আমাদের প্রথমে সংজ্ঞায়িত করতে হবে। এখানে, গ্রাফ বলতে সমতলে অঙ্কিত কোনো ফাংশনাল গ্রাফকে বোঝানো হচ্ছে না, বরং এটি একটি ডেটা স্ট্রাকচার যা এক সেট ভার্টেক্স এবং সেগুলোকে সংযোগকারী এজ নিয়ে গঠিত। উদাহরণস্বরূপ, যদি আমরা ভার্টেক্সগুলোকে সাবওয়ে স্টেশন বা বাস স্টপ হিসেবে ভাবি, তাহলে এজগুলো হবে সেই ভার্টেক্সগুলোকে সংযোগকারী রেললাইন বা রাস্তা।
এজগুলোর সাথে ওয়েট বা ওজন নির্ধারিত থাকতে পারে; এই মানগুলো পরিমাপযোগ্য খরচকে বোঝায়, যেমন দুটি ভার্টেক্সের মধ্যে যাতায়াতের জন্য প্রয়োজনীয় দূরত্ব বা সময়। এছাড়াও, যদি এজগুলোর দিক থাকে, তবে গ্রাফটি একটি “ডিরেক্টেড গ্রাফ” বা নির্দেশিত গ্রাফে পরিণত হয়, যেখানে শুধুমাত্র তীরের দিকেই চলাচল করা যায়। ডাইকস্ট্রার অ্যালগরিদম এই ধরনের একটি গ্রাফের একটি নির্দিষ্ট প্রারম্ভিক বিন্দু থেকে অন্য প্রতিটি ভার্টেক্স পর্যন্ত সংক্ষিপ্ততম দূরত্ব এবং পথ গণনা করে।

ডাইকস্ট্রা অ্যালগরিদম কীভাবে কাজ করে

চলুন একটি সাধারণ উদাহরণ দিয়ে অ্যালগরিদমটি ব্যাখ্যা করা যাক। শুরুর ভার্টেক্সের প্রাথমিক মান ০ ধরা হয়, এবং অন্য সব ভার্টেক্সের প্রাথমিক মান অসীম (∞) ধরা হয়, যার অর্থ হলো এখনও কোনো সংযোগের তথ্য নেই। এই মানগুলো “শুরুর বিন্দু থেকে ওই ভার্টেক্সে পৌঁছানোর জন্য এখন পর্যন্ত জানা সর্বনিম্ন দূরত্ব (বা সময়)”-কে নির্দেশ করে।
প্রথম ধাপে (ধাপ ১), আমরা প্রারম্ভিক ভার্টেক্সকে ০ ধরে শুরু করি। দ্বিতীয় ধাপে (ধাপ ২), প্রারম্ভিক ভার্টেক্স থেকে সরাসরি পৌঁছানো যায় এমন সমস্ত প্রতিবেশী ভার্টেক্সের জন্য, আমরা সংশ্লিষ্ট এজের ওয়েটের সাথে প্রারম্ভিক ভার্টেক্সের মান (০) যোগ করে প্রতিটির জন্য একটি অস্থায়ী মান রেকর্ড করি। উদাহরণে, এই মানগুলো ৮, ৯, এবং ১১ হিসাবে রেকর্ড করা হয়েছে। এই পর্যায়ে, প্রারম্ভিক ভার্টেক্সের প্রক্রিয়াকরণ সম্পন্ন হয়।
“প্রসেসড ভার্টেক্স” বলতে এমন একটি ভার্টেক্সকে বোঝায় যার জন্য কোনো সংক্ষিপ্ততর পথ খুঁজে পাওয়া যায় না, অর্থাৎ এর চূড়ান্ত সংক্ষিপ্ততম দূরত্ব নির্ধারণ করা হয়ে গেছে। ডাইকস্ট্রার অ্যালগরিদমে, একবার কোনো ভার্টেক্সের সংক্ষিপ্ততম দূরত্ব এইভাবে নির্ধারণ করা হয়ে গেলে, সেই ভার্টেক্সটিকে প্রসেসড হিসেবে চিহ্নিত করা হয় এবং এর মান আর কখনো পরিবর্তন করা হয় না।
তৃতীয় ধাপে (ধাপ ৩), আমরা এখন পর্যন্ত রেকর্ড করা অস্থায়ী মানগুলোর মধ্যে সর্বনিম্ন মানের ভার্টেক্সটি নির্বাচন করি। উদাহরণস্বরূপ, ৮ মানের ভার্টেক্সটি নির্বাচন করা হয়। এই ভার্টেক্স থেকে শুরু করে, প্রারম্ভিক বিন্দু থেকে এই ভার্টেক্স পর্যন্ত দূরত্বগুলো ব্যবহার করে এর চারপাশের ভার্টেক্সগুলোর মান আপডেট করা হয়। এই প্রক্রিয়ার মাধ্যমে আপডেটগুলো সম্পন্ন হয়—উদাহরণস্বরূপ, কিছু সংলগ্ন ভার্টেক্সের জন্য নতুন সম্ভাব্য দূরত্ব ১৮ হিসাবে গণনা করা হয়। এই ভার্টেক্সটির প্রক্রিয়াকরণ সম্পূর্ণ হলে, এটিকে প্রক্রিয়াকৃত হিসাবেও চিহ্নিত করা হয়।
চতুর্থ ধাপে (ধাপ ৪), আমরা পরবর্তী ক্ষুদ্রতম মানযুক্ত ভার্টেক্সটি নিয়ে কাজ করি—এই উদাহরণে, যেটির মান ৯। এই ভার্টেক্সটির জন্যও, আমরা একই পদ্ধতিতে এর সংলগ্ন ভার্টেক্সগুলোর সম্ভাব্য দূরত্ব গণনা করি। এই প্রক্রিয়ার সময়, যেসব ভার্টেক্সে ইতিমধ্যে মান নির্ধারিত আছে, সেগুলোর জন্য নতুন সম্ভাব্য মান (যেমন, ১৫, ১০, ১২) দেখা দিতে পারে। যদি নতুন মানটি বিদ্যমান মানের চেয়ে ছোট হয়, তবে এটি আগের মানটিকে বাতিল করে দেয়; অন্যথায়, মূল মানটি অপরিবর্তিত থাকে। এই প্রক্রিয়াটিকে “এজ রিলাক্সেশন” বলা হয়, এবং এটি একটি প্রয়োজনীয় পদ্ধতি কারণ আমরা সর্বদা ক্ষুদ্রতম পথটিই খুঁজে থাকি।
পঞ্চম ধাপ (ধাপ ৫) থেকে একই পদ্ধতি পুনরাবৃত্তি করা হয়। প্রতিবার, এখনো প্রক্রিয়াকৃত হয়নি এমন ভার্টেক্সগুলোর মধ্যে সর্বনিম্ন অস্থায়ী মানযুক্ত ভার্টেক্সটি নির্বাচন করা হয় এবং এর সংলগ্ন এজগুলোর মাধ্যমে এর সংলগ্ন ভার্টেক্সগুলোর অস্থায়ী মান শিথিল করে হালনাগাদ করা হয়। সমস্ত ভার্টেক্স প্রক্রিয়াকৃত না হওয়া পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি করার মাধ্যমে, আমরা প্রারম্ভিক বিন্দু থেকে প্রতিটি ভার্টেক্স পর্যন্ত সংক্ষিপ্ততম দূরত্ব এবং সংক্ষিপ্ততম পথগুলো নির্ধারণ করতে পারি।

প্রয়োগের উদাহরণ: নেটওয়ার্ক এবং রাউটার

কম্পিউটার নেটওয়ার্ক এমন একটি ক্ষেত্রের প্রধান উদাহরণ যেখানে ডাইকস্ট্রার অ্যালগরিদম বাস্তবে ব্যাপকভাবে ব্যবহৃত হয়। যেহেতু কোটি কোটি ডিভাইসকে সরাসরি একটি নেটওয়ার্কে সংযুক্ত করা অদক্ষতার পরিচায়ক—যেমনটা ইন্টারনেটের ক্ষেত্রে দেখা যায়—তাই কাছাকাছি থাকা ডিভাইসগুলো স্থানীয় নেটওয়ার্ক গঠন করে, যা পরবর্তীতে একটি স্তরক্রমিক কাঠামোতে উচ্চ-স্তরের নেটওয়ার্কের সাথে সংযুক্ত হয়। এই ধরনের জটিল সংযোগ কাঠামোতে, একটি ডিভাইস থেকে অন্য ডিভাইসে যাওয়ার অগণিত পথ থাকে।
একটি নেটওয়ার্কে, প্রতিটি নোডকে (যেমন একটি রাউটার) নির্দিষ্ট খরচের (ব্যান্ডউইথ, ল্যাটেন্সি, ইত্যাদি) উপর ভিত্তি করে পথগুলো মূল্যায়ন করতে হয় এবং গন্তব্যে পৌঁছানোর জন্য "দ্রুততম" বা "সর্বনিম্ন খরচের" পথটি খুঁজে বের করতে হয়। রাউটারগুলো সর্বোত্তম পথ—অর্থাৎ পরবর্তী হপ—নির্ধারণ করার জন্য শর্টেস্ট-পাথ অ্যালগরিদম, যেমন ডাইকস্ট্রার অ্যালগরিদম, ব্যবহার করে, যেখানে তাদের ট্র্যাফিক ফরওয়ার্ড করা উচিত। তবে, যেহেতু রিয়েল-টাইম ট্র্যাফিকের অবস্থা ক্রমাগত পরিবর্তিত হতে থাকে, তাই একটি রাউটারের একটি নির্দিষ্ট, সম্পূর্ণ পথ ঘোষণা করার পরিবর্তে প্রতিটি রাউটারের জন্য শুধুমাত্র তার ঠিক পরবর্তী নেটওয়ার্ক সেগমেন্ট সম্পর্কে তথ্য প্রদান করা এবং পথটি তৈরি হওয়ার সাথে সাথে প্রতিটি রাউটারের এই তথ্য আপডেট করা অধিকতর বাস্তবসম্মত।

উপসংহার: পথনির্দেশনা থেকে প্রাপ্ত শিক্ষা

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