রাস্তার দৈর্ঘ্য আলাদা হলে এক জায়গা থেকে বাকি সব জায়গায় যাওয়ার সবচেয়ে কম খরচের পথ।
মূল ধারণা (GPS)
BFS সবচেয়ে কম রাস্তা দিয়ে যাওয়া path খুঁজে পায়, কিন্তু বাস্তবে রাস্তার দৈর্ঘ্য আলাদা আলাদা। Dijkstra খুঁজে পায় সবচেয়ে কম মোট দৈর্ঘ্যের path। এটা প্রতিটি জায়গার এখন পর্যন্ত জানা সেরা distance একটি খাতায় লিখে রাখে, শুরুতে start ছাড়া সব জায়গায় ∞ (অজানা), আর start-এ 0।
যে জায়গার কাজ এখনো শেষ হয়নি, তার মধ্যে সবচেয়ে ছোট জানা distance যার, সেটা বেছে নিন। এর চেয়ে ভালো কিছু হতে পারে না, কারণ অন্য যেকোনো route-কে এমন একটি জায়গা দিয়ে আসতে হবে যা ইতিমধ্যে আরও দূরে। তাই এর distance final।
সেখান থেকে প্রতিটি রাস্তা try করুন: এখন পর্যন্ত distance + রাস্তার দৈর্ঘ্য কি neighbor-এর জন্য খাতায় লেখা মানের চেয়ে ছোট? হলে edge-টি relax করুন, অর্থাৎ খাতা update করুন।
কিছু বাকি না থাকা পর্যন্ত বারবার করুন।
"সবচেয়ে ছোটটা বেছে নেওয়া" ধাপটা একটি priority queue (min-heap, heap page দেখুন)। এর জন্য প্রতিটি রাস্তার দৈর্ঘ্য অবশ্যই positive হতে হবে।
Run করে দেখুন
রাস্তা দুই দিকেই কাজ করে। Node গুলোর নম্বর 0, 1, 2, ... এভাবে, ফাঁক ছাড়া (সর্বোচ্চ 10টি node, 15টি রাস্তা)। দৈর্ঘ্য 1 থেকে 99-এর মধ্যে integer।
নিজে চেষ্টা করুন
Default graph দেখুন। সরাসরি রাস্তা 0–1-এর দৈর্ঘ্য 4, কিন্তু node 1-এর উত্তর 3। কোন route জিতছে?
0-1:4 বদলে 0-1:2 করুন এবং আবার run করুন। কী বদলায়?
বাকিদের সাথে রাস্তা নেই এমন node রাখুন, যেমন 0-1:1, 2-3:1 (start 0)। 2 আর 3-এর distance কী থাকে?
"stale entry" ধাপটা খেয়াল করুন: যে node আগেই ভালো distance পেয়ে গেছে, তার জন্য queue-তে পুরনো, বড় distance-এর entry থেকে যেতে পারে।
সাধারণ ভুল
Negative রাস্তার দৈর্ঘ্য। Dijkstra ধরে নেয় যে শেষ হয়ে যাওয়া node-এর distance আর কমানো যাবে না। Negative edge এই ধারণা ভেঙে দেয় (এর বদলে Bellman-Ford ব্যবহার করুন)।
stale check ভুলে যাওয়া।if cur.dist > dist[cur.node] { continue } না থাকলে পুরনো queue entry-র জন্য একই কাজ আবার করতে হয়।
সাধারণ queue ব্যবহার করা। এটাকে সবসময় সবচেয়ে ছোট distance ফেরত দিতে হবে, সবচেয়ে পুরনো entry নয়।
0-কে "infinity" ধরা। অজানা distance-এর জন্য খুব বড় একটি সংখ্যা (অথবা presence check সহ map) ব্যবহার করুন।
Complexity, সহজ ভাষায়: প্রতিটি রাস্তা priority queue-তে সর্বোচ্চ একটি entry যোগ করতে পারে, আর প্রতিটি queue operation-এর খরচ প্রায় log(entry-সংখ্যা)। তাই time complexity প্রায় O((V + E) log V)। বড় map-এও এটা দ্রুত, তবে distance আর queue-র জন্য memory লাগে।