মডিউল ৬_৫ঃ Dijkstra Optimize Approach

আমরা এখন Dijkstra এর অপ্টিমাইজ ভারশন নিয়ে কাজ করব। খুব সামান্য পরিবর্তন এর মাধ্যমেই এটি করা সম্ভব।সেটি হচ্ছে আমরা কিউ এর পরিবর্তে priority queue ব্যবহার করব।

এই গ্রাফে ০ কে সোর্স ধরে যদি আমরা Dijkstra শুরু করি প্রথমে সব আগের মতোই থাকবে। আমরা একটা ডিস্টেন্স এ্যারে মেইন্টেইন করব ও পাথ রিলেক্স করা যায় কিনা দেখব।

(০,০) নোডটাকে priority queue তে পুশ করব ও এমন ভাবে priority queue টা সেট করব যাতে আমাকে মিনিমাম ওয়েটেড নোডটা ফ্রন্ট এলিমেন্ট হিসেবে দেই।

এবার (০,০) কে ফ্রন্ট ভ্যালু হিসেবে নিব এবং পপ করে দিব। এবার ০ এর চাইল্ড গুলোর পাথ রিলেক্স করার চেষ্টা করব আর যদি করা যায় তাহলে তাদেরকে priority queue তে পুশ করে দিব।

যেমন ০ থেকে ১ এ যেতে,

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

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

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

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

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

এবার priority queue এর ফ্রন্ট ভ্যালুকে নিব যেটি হচ্ছে ২ আর ২ কে পপ করে দিব।

২ থেকে ০ তে যাওয়া যায় কিন্ত সেটি অলরেডি রিল্যাক্সড তাই সেটিতে যাবো না। ২ থেকে ১ এ যাওয়া যায় সেই ক্ষেত্রে,

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

তাই ১ রিল্যাক্স হবে ও এর ভ্যালু distance array এবং priority queue তে আপডেট হবে।

২ থেকে ৩ এ যাওয়া যায় সেই ক্ষেত্রে,

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

তাই ৩ রিল্যাক্স হবে ও এর ভ্যালু distance array এবং priority queue তে আপডেট হবে।

এবার priority queue এর ফ্রন্ট ভ্যালুকে নিব যেটি হচ্ছে ১ আর ১ কে পপ করে দিব।

১ থেকে ০ তে যাওয়া যায় কিন্ত সেটি অলরেডি রিল্যাক্সড তাই সেটিতে যাবো না। ১ থেকে ২ এও যাওয়া যায় কিন্ত সেটিও অলরেডি রিল্যাক্সড তাই এটিও আপডেট হবে না। ১ থেকে ৩ এও যাওয়া যায় তবে সেটিও রিল্যাক্স হবে না কেননা,

dis[1]+cost(1,3) = 5+7 = 12>5

এবার priority queue এর ফ্রন্ট ভ্যালুকে নিব যেটি হচ্ছে ১ আর ১ কে পপ করে দিব। কিন্ত চিন্তা করে দেখো ১ এর অলরেডি কম কস্ট এর ভ্যালু নিয়ে আমরা কাজ করে ফেলেছি তাই আমরা এখানেও কোনো আপডেট করব না।

এবার priority queue এর ফ্রন্ট ভ্যালুকে নিব যেটি হচ্ছে ৩ আর ৩ কে পপ করে দিব।

৩ থেকে ২ আর ১ এ যাওয়া যায় তবে ২ আর ১ অলরেডি রিল্যাক্সড হওয়ার এখন আর কোনো আপডেট হবে না।

এবার যেহেতু priority queue এম্পটি হয়ে গেছে আমরা বলতে পারি আমাদের কাজ শেষ । এখন যদি distance array এর দিকে তাকায় তাহলে আমরা সোর্স থেকে সকল নোড এর শর্টেস্ট ডিস্টেন্স পেয়ে যাবো।