Dijkstra’s Shortest Path

রাস্তার দৈর্ঘ্য আলাদা হলে এক জায়গা থেকে বাকি সব জায়গায় যাওয়ার সবচেয়ে কম খরচের পথ।

মূল ধারণা (GPS)

BFS সবচেয়ে কম রাস্তা দিয়ে যাওয়া path খুঁজে পায়, কিন্তু বাস্তবে রাস্তার দৈর্ঘ্য আলাদা আলাদা। Dijkstra খুঁজে পায় সবচেয়ে কম মোট দৈর্ঘ্যের path। এটা প্রতিটি জায়গার এখন পর্যন্ত জানা সেরা distance একটি খাতায় লিখে রাখে, শুরুতে start ছাড়া সব জায়গায় ∞ (অজানা), আর start-এ 0।

  1. যে জায়গার কাজ এখনো শেষ হয়নি, তার মধ্যে সবচেয়ে ছোট জানা distance যার, সেটা বেছে নিন। এর চেয়ে ভালো কিছু হতে পারে না, কারণ অন্য যেকোনো route-কে এমন একটি জায়গা দিয়ে আসতে হবে যা ইতিমধ্যে আরও দূরে। তাই এর distance final।
  2. সেখান থেকে প্রতিটি রাস্তা try করুন: এখন পর্যন্ত distance + রাস্তার দৈর্ঘ্য কি neighbor-এর জন্য খাতায় লেখা মানের চেয়ে ছোট? হলে edge-টি relax করুন, অর্থাৎ খাতা update করুন।
  3. কিছু বাকি না থাকা পর্যন্ত বারবার করুন।

"সবচেয়ে ছোটটা বেছে নেওয়া" ধাপটা একটি priority queue (min-heap, heap page দেখুন)। এর জন্য প্রতিটি রাস্তার দৈর্ঘ্য অবশ্যই positive হতে হবে।

Run করে দেখুন

রাস্তা দুই দিকেই কাজ করে। Node গুলোর নম্বর 0, 1, 2, ... এভাবে, ফাঁক ছাড়া (সর্বোচ্চ 10টি node, 15টি রাস্তা)। দৈর্ঘ্য 1 থেকে 99-এর মধ্যে integer।

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: প্রতিটি রাস্তা priority queue-তে সর্বোচ্চ একটি entry যোগ করতে পারে, আর প্রতিটি queue operation-এর খরচ প্রায় log(entry-সংখ্যা)। তাই time complexity প্রায় O((V + E) log V)। বড় map-এও এটা দ্রুত, তবে distance আর queue-র জন্য memory লাগে।