গ্রাফপড়তে ৬ মিনিট লাগবে

ডাইকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm)

গ্রাফের জিপিএস (GPS) — এক জায়গা থেকে বাকি সব জায়গায় যানয়ার সবচেয়ে সস্তা বা ছোট রাস্তা বের করা

time with heap: O((V+E) log V)time with array: O(V²)space: O(V)

সব রাস্তার দূরত্ব বা খরচ যখন সমান থাকে, তখন সবচেয়ে ছোট রাস্তা (Shortest Path) বের করতে BFS দারুণ কাজ করে। কিন্তু বাস্তব দুনিয়ার ম্যাপে সব রাস্তার দূরত্ব বা জ্যাম তো আর একরকম হয় না! আলাদা আলাদা খরচ বা দূরত্বের রাস্তায় সবচেয়ে দ্রুত যানয়ার উপায় বের করতেই দরকার হয় ডাইকস্ট্রা অ্যালগরিদম (Dijkstra's algorithm)।

এটাকে আপনার গাড়ির জিপিএস বা গুগল ম্যাপস (Google Maps) এর মতো ভাবতে পারেন। সে সব রাস্তার স্পিড বা দূরত্বের খবর রাখে এবং সবসময় চেক করতে থাকে যে পরবর্তী কোন রাস্তা ধরলে সবচেয়ে দ্রুত পৌঁছানো যাবে। একটা ব্যাপার মাথায় রাখতে হবে: ডাইকস্ট্রা শুধু পজিটিভ বা শূন্য (non-negative) ওজনের বা দূরত্বের রাস্তাতেই কাজ করে। যদি কোনো রাস্তার ওজন মাইনাস বা নেগেটিভ হয়, তাহলে এর বদলে বেলম্যান-ফোর্ড (Bellman-Ford) ব্যবহার করতে হবে।

আসল ট্রিক: সবসময় সবচেয়ে সস্তা বা কাছের নোডটাকে আগে টার্গেট করুন

সবগুলো শহরের দূরত্বের হিসাব রাখার জন্য একটা ডিস্ট্যান্স টেবিল (Distance table) বানান — শুরুর শহরটার দূরত্ব হবে 0, আর বাকি সব অসীমে বা অনেক দূরে (Infinity) আছে ধরে নিন। এবার একটা মিন-হিপ (Min-heap) ব্যবহার করুন, যাতে সবসময় সবচেয়ে কম খরচের বা কাছের শহরটাই আগে আপনার হাতে আসে। যখনই একটা শহরে পৌঁছাবেন, তখন চেক করে দেখুন সেই শহর দিয়ে তার আশপাশের শহরগুলোতে আরও কম খরচে পৌঁছানো যায় কি না। যদি যায়, তবে সেই শহরের লিস্টআপ করা দূরত্বটা আপডেট (Relax) করে দিন।

pseudocode

function dijkstra(graph, start):
  dist = { সব শহর: Infinity }
  dist[start] = 0
  heap = MinHeap()
  heap.push([0, start])

  while heap ফাঁকা না হয়:
    [d, node] = heap.pop()
    if d > dist[node]: continue  // এটা পুরনো বা বাতিল এন্ট্রি

    for [neighbor, weight] of graph[node]:
      newDist = dist[node] + weight
      if newDist < dist[neighbor]:
        dist[neighbor] = newDist
        heap.push([newDist, neighbor])

  return dist

◈ দেখুন কীভাবে একে একে শর্টেস্ট রুট বের হয় আর ডিস্ট্যান্স টেবিল আপডেট হয়

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

এই লোভী (Greedy) বুদ্ধিটা কেন কাজ দেয়?

যেহেতু কোনো রাস্তার দূরত্ব বা খরচ নেগেটিভ হয় না, তাই মিন-হিপ (Min-heap) থেকে যখন d দূরত্বের কোনো শহরকে বের করা হয়, তার মানে হলো—ওই শহরে এর চেয়ে কম খরচে বা ছোট রাস্তায় যানয়ার আর কোনো উপায় পৃথিবীতে নেই। কারণ পরে আর যে রাস্তাই আপনি আবিষ্কার করুন না কেন, সেটাকে আরো বড় বা সমান দূরত্বের রাস্তা পার হয়েই আসতে হবে, মানে খরচ আরো বাড়বে ছাড়া কমবে না। ডাইকস্ট্রার এই একটা গ্যারান্টির ওপর ভর করেই পুরো অ্যালগরিদমটা নির্ভুল কাজ করে।

পুরো রাস্তাটা বের করা

শুধু দূরত্ব জানলে তো হবে না, কোন দিক দিয়ে যেতে হবে সেটাও জানা চাই। এর জন্য একটা prev বা আগের নোডের টেবিল মেইনটেইন করুন: যখনই কোনো প্রতিবেশীর দূরত্ব আপডেট (relax) করবেন, তখনই লিখে রাখুন যে prev[প্রতিবেশী] = বর্তমান শহর। কাজ শেষ হলে গন্তব্য বা ডেস্টিনেশন থেকে পেছন দিকে এই prev টেবিল ধরে হাঁটলেই পুরো রুট বা রাস্তাটা চোখের সামনে ভেসে উঠবে।

হিপ (Heap) বনাম সাধারণ অ্যারে (Array)

মিন-হিপ (Min-heap) ব্যবহার করলে স্পিড পাওয়া যায় O((V+E) log V)। আর যদি সাধারণ অ্যারে ব্যবহার করে প্রতিবার লুপ চালিয়ে সবচেয়ে ছোটটা খুঁজতে যান, তবে লাগবে O(V²)। যখন ম্যাপে রাস্তা কম (Sparse graph) থাকে, তখন হিপ অনেক ফাস্ট কাজ করে। তবে যদি রাস্তা অনেক অনেক বেশি (Dense graph) থাকে, তখন দুটোর পারফরম্যান্সের খুব একটা পার্থক্য থাকে না।

দ্রষ্টব্য: নেগেটিভ বা ঋনাত্মক (Negative) এজ বা রাস্তা থাকলে ডাইকস্ট্রা কাজ করে না। কারণ নেগেটিভ রাস্তার জন্য এমন হতে পারে যে, অনেক ঘুরে আসা একটা রাস্তা হঠাৎ করে বেশি সস্তা হয়ে যেতে পারে — যা ডাইকস্ট্রার সেই গ্যারান্টিটাকে ভেঙে দেয়। নেগেটিভ রাস্তার জন্য বেলম্যান-ফোর্ড (Bellman-Ford) ব্যবহার করুন।