মডিউল ৬_২ঃ পাথ রিলেক্সেশন

আমরা Dijkstra সম্পর্কে জানার আগে আরো একটি টপিক সম্পর্কে জানব সেটি হচ্ছে পাথ রিলেক্সেশন।

ধর তুমি C নোড এ আছো আর তুমি B নোড এ যেতে চাও। তোমার কাছে B->C তে যাওয়ার জন্য একটি ডাইরেক্ট রাস্তা আছে যার কস্ট ৫০। এখন ধর তুমি C->A তে যেতে পারো এবং সেখান থেকে B তে যেতে পারো। তাহলে এই রাস্তা দিয়ে B তে পোছাতে খরচ হবে Distannce of C->A + Distance of A->B = 35| যেহেতু এটি ৫০ থেকে কম তাহলে আমরা বলতে পারি B তে যাওয়ার Distance 35|

তাহলে পাথ রিলেক্সেশনে আমরা বলতে পারি,

if dis[a]+x < dis[b] হয়,

dis[b] = dis[a]+x