মডিউল ৬_৩ঃ Dijkstra Naive Approach

আমরা এখন Dijkstra এলগোরিদমের Naive ভারশনটা শিখব।

বিএফএস নিশ্চয়ই তুমি ভালো করে বুঝো। বিএফএস এ আমাদের একটা নোডে কখনো দুইবার যাওয়া দরকার হয়নি, আমরা প্রতিবার দেখেছি একটা নোড ভিজিটেড কিনা, যদি ভিজিটেড না হয় তাহলে সেই নোডকে কিউতে পুশ করে দিয়েছি এবং ডিসটেন্স ১ বাড়িয়ে দিয়েছি। Dijkstra তে আমরা একই ভাবে কিউ তে নোড রাখবো তবে ভিজিটেড দিয়ে আপডেট না করে নতুন এজকে “রিল্যাক্স” বা আপডেট করবো।

উপরের গ্রাফটাই খেয়াল করি। ধরি এখানে সোর্স নোড হচ্ছে ০ । এখন আমরা distance এ্যারে মেইন্টেইন করবো।

শুরুতে সোর্স নোড এর ডিস্টেন্স ০ ধরি ও বাকি সকল নোড এর ডিস্টেন্স infinite ধরি।

এবার একটি কিউ মেইনটেইন করব ও কিউ এর ফ্রন্ট এ সোর্স নোড ও তার কস্টকে ডিস্টেন্সকে পুশ করব।

এবার কিউ এর ফ্রন্ট এলিমেন্ট অর্থাৎ ০ কে নিব ও পপ করে দিব। ০ থেকে যে সকল নোড এ যাওয়া যায় তাদের পাথ রিলেক্স করা যায় কিনা দেখব। যেমন ০ থেকে ১ এ যেতে,

dis[0]+cost(0,1) = 0+5 = 5 < dis[1](infinity)

তাই ১ এর নতুন distance কে distance array তে আপডেট করব আর ১ কে ও তার distance কে কিউতে পুশ করব।

০ থেকে ২ এও যাওয়া যায়।

dis[0]+cost(0,2) = 0+2 = 2< dis[2](infinity)

তাই ২ এর নতুন distance কে distance array তে আপডেট করব আর ২কে ও তার distance কে কিউতে পুশ করব।

এখন কিউ এর ফ্রন্ট এলিমেন্টকে আবার নিব এবং তাকে পপ করে দিব। এখন সেটি হচ্ছে ১।১ থেকে যে সকল নোড এ যাওয়া যায় তাদের পাথ রিলেক্স করা যায় কিনা দেখব। ১ থেকে কোনো নোড এ যাওয়া যায় না। তাই এই স্টেপ এ কোনো আপডেট হবে না।

এবার কিউ এর ফ্রন্ট এলিমেন্ট অর্থাৎ ২ কে নিব ও পপ করে দিব। ২ থেকে যে সকল নোড এ যাওয়া যায় তাদের পাথ রিলেক্স করা যায় কিনা দেখব। যেমন ২ থেকে ৩এ যেতে,

dis[2]+cost(2,3) = 2+3 = 5 < dis[3](infinity)

তাই ৩ এর নতুন distance কে distance array তে আপডেট করব আর ৩ কে ও তার distance কে কিউতে পুশ করব।

আবার ২ থেকে ১ এও যাওয়া যায়। ২থেকে ১ এ গেলে ১ এর পাথ রিল্যাক্স হবে কেননা

dis[2]+cost(2,1)=2+1=3<5

তাই ১ এর নতুন distance কে distance array তে আপডেট করব আর ৩ কে ও তার distance কে কিউতে পুশ করব।

এখন কিউ এর ফ্রন্ট এলিমেন্টকে আবার নিব এবং তাকে পপ করে দিব। এখন সেটি হচ্ছে ৩।৩ থেকে যে সকল নোড এ যাওয়া যায় তাদের পাথ রিলেক্স করা যায় কিনা দেখব। ৩ থেকে কোনো নোড এ যাওয়া যায় না। তাই এই স্টেপ এ কোনো আপডেট হবে না।

এখন কিউ এর ফ্রন্ট এলিমেন্টকে আবার নিব এবং তাকে পপ করে দিব। এখন সেটি হচ্ছে ১।১ থেকে যে সকল নোড এ যাওয়া যায় তাদের পাথ রিলেক্স করা যায় কিনা দেখব। ১ থেকে কোনো নোড এ যাওয়া যায় না। তাই এই স্টেপ এ কোনো আপডেট হবে না।

এখন যেহেতু কিউটা এম্পটি হয়ে গেছে তার মানে আমাদের কাজ শেষ । এবার যদি Distance এ্যারেটার দিকে তাকায় তাহলে বুঝব যে ০ থেকে প্রতিটা নোড এ যাওয়ার শর্টেস্ট ডিস্টেন্স আমরা পেয়ে গেছি।