গ্রাফ অ্যালগরিদম৯ মিনিট পড়া

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

সর্বদা প্রথমে সবচেয়ে সস্তা রাস্তাটি বেছে নিন — গ্রাফের জন্য জিপিএস নেভিগেশন

binary heap:O((V+E) log V)Fibonacci heap:O(E + V log V)requirement:কোনো নেগেটিভ এজ ওয়েট থাকা যাবে না

ধরুন আপনি একটি ভ্রমণের পরিকল্পনা করছেন। আপনি আপনার শহর থেকে অন্য প্রতিটি শহরে যাওয়ার সবচেয়ে সস্তা পথ চান। আপনার জিপিএস কৌশল: সর্বদা পরবর্তী সবচেয়ে সস্তা পৌঁছানো যায় এমন রাস্তার দিকে এগোনো।

বাড়ি থেকে শুরু করুন (কস্ট 0)। বাড়ি থেকে বের হওয়া সমস্ত রাস্তা দেখুন, সেগুলোর কস্ট লিখে রাখুন। সবচেয়ে সস্তা কোনটি? সেটিকে চূড়ান্ত করে নিন — সেই গন্তব্যের ক্ষুদ্রতম পথ নিশ্চিত হয়ে গেল। সেখান থেকে, সেই শহর থেকে বের হওয়া সমস্ত রাস্তা দেখুন। যদি আপনি কোনো সস্তা পথ পান, তবে কস্ট আপডেট করুন। সর্বদা আনভিজিটেড (unvisited) বা পরিদর্শন করা হয়নি এমন গন্তব্যগুলোর মধ্যে সবচেয়ে সস্তা গন্তব্যটি বেছে নিন। এভাবেই আপনার সব জায়গায় পৌঁছানো পর্যন্ত পুনরাবৃত্তি করুন।

এটিই হলো ডাইকস্ট্রার অ্যালগরিদম (Dijkstra's Algorithm) — এটি একটি গ্রিডি (greedy) কৌশল যা কাজ করে কারণ নন-নেগেটিভ রাস্তার কস্ট মানে হলো আপনি আরও দূরে গিয়ে কখনোই একটি পথকে আরও সস্তা করতে পারবেন না।

রিল্যাক্সেশন প্রক্রিয়া (The Relaxation Step)

প্রতিটি নোড বা ভার্টেক্স v এর একটি প্রাথমিক দূরত্ব dist[v] থাকে, যা শুরুতে অসীম (infinity) ধরা হয় (কারণ সেখানে পৌঁছানোর পথ অজানা), শুধুমাত্র সোর্স নোড ছাড়া (dist[s] = 0)।

রিল্যাক্সেশন (Relaxation): যখন u ভার্টেক্সটি প্রসেস করছেন, এর প্রতিটি প্রতিবেশী v এর জন্য চেক করুন: "আমরা এখনও পর্যন্ত যে পথ পেয়েছি, তার চেয়ে কি u হয়ে v তে যাওয়া বেশি সস্তা?" যদি dist[u] + weight(u,v) < dist[v] হয়, তবে dist[v] আপডেট করুন। অ্যালগরিদমটির মূল কাজ কেবল এটুকুই। এরপর কোন ভার্টেক্সটিকে রিল্যাক্স করতে হবে তা বেছে নেওয়া হয় (সর্বদা সেই ভার্টেক্স যার বর্তমান dist সবচেয়ে কম) এবং সব ভার্টেক্স চূড়ান্ত না হওয়া পর্যন্ত এটি চলতে থাকে।

প্রায়োরিটি কিউ (Priority Queue) কেন দরকার?

মূল প্রশ্ন হলো: "আনভিজিটেড ভার্টেক্সগুলোর মধ্যে কোনটির বর্তমান দূরত্ব সবচেয়ে কম?" একটি বাইনারি মিন-হিপ (binary min-heap) এর উত্তর প্রতিটি এক্সট্রাকশনে O(log V) সময়ে দিতে পারে। এতে মোট সময় লাগে: O((V+E) log V) — যা স্পার্স (sparse) গ্রাফের ক্ষেত্রে প্রায় রৈখিক বা লিনিয়ার (near-linear)।

বাস্তবে, বেশিরভাগ ইমপ্লিমেন্টেশন একটি লেজি ডিলিশন (lazy deletion) বা অলস মুছে ফেলার পদ্ধতি ব্যবহার করে: যখন আপনি v এর একটি ছোট পথ পান, তখন কেবল হিপের মধ্যে একটি নতুন এন্ট্রি (dist, v) পুশ করুন। যখন আপনি একটি ভার্টেক্স বের করেন এবং দেখেন যে এর স্টোর করা দূরত্ব বর্তমান dist[v] এর চেয়ে বেশি, তার মানে এটি পুরনো বা স্টেল (stale) — তখন এটিকে এড়িয়ে যান। এর ফলে ডিক্রিজ-কি (decrease-key) অপারেশনের প্রয়োজন হয় ঘন ঘন, তবুও আমরা একই অ্যাসিম্পটোটিক কমপ্লেক্সিটি পাই।

নেগেটিভ ওয়েট কেন সমস্যা তৈরি করে?

ডাইকস্ট্রার নির্ভুলতা একটি গ্যারান্টির ওপর দাঁড়িয়ে আছে: একবার একটি ভার্টেক্স চূড়ান্ত হয়ে গেলে, এর দিকে কোনো ছোট পথ আর কখনোই পাওয়া যাবে না। নন-নেগেটিভ ওয়েটের ক্ষেত্রে, আরও এজ যোগ করলে দীর্ঘপথের দৈর্ঘ্য বাড়বে বা একই থাকবে — তাই ন্যূনতম আনভিজিটেড ভার্টেক্সকে চূড়ান্ত করা সবসময় নিরাপদ।

একটিমাত্র নেগেটিভ এজ এই নিয়ম ভেঙে দিতে পারে। ধরুন ৫ দূরত্বের ভার্টেক্স v চূড়ান্ত করা হলো। পরে আপনি u → v এজের সন্ধান পেলেন যার ওয়েট −৩, ফলে মোট দূরত্ব হয় ৪। ডাইকস্ট্রা এটি মিস করবে। যেসব গ্রাফে নেগেটিভ ওয়েট আছে, সেগুলোর জন্য আপনাকে বেলম্যান-ফোর্ড (Bellman-Ford) অ্যালগরিদম ব্যবহার করতে হবে।

ডেনস বনাম স্পার্স গ্রাফ (Dense vs. Sparse Graphs)

স্পার্স গ্রাফে (Sparse graphs) (E ≈ V), হিপ-ভিত্তিক O((V+E) log V) ≈ O(V log V) অত্যন্ত চমৎকার কাজ করে। তবে ডেনস গ্রাফে (Dense graphs) (E ≈ V²), একটি সহজ O(V²) অ্যারে স্ক্যান (সর্বনিম্ন মান খুঁজতে লিনিয়ার সার্চ) আসলে হিপ-ভিত্তিক ভার্সনের চেয়ে ভালো পারফর্ম করতে পারে, কারণ O(V² log V) > O(V²)।

দ্রষ্টব্য: ডাইকস্ট্রা হলো একটি গ্রিডি অ্যালগরিদম: এটি বাজি ধরে যে আমরা এপর্যন্ত সবচেয়ে সস্তা পৌঁছানো যায় এমন ভার্টেক্সে সর্বোত্তমভাবেই পৌঁছেছি। নন-নেগেটিভ ওয়েটের ক্ষেত্রে, এই বাজি সবসময় সঠিক হয় — ভবিষ্যতের কোনো পথ এসে আরও সস্তা হতে পারে না। নেগেটিভ ওয়েট এই বাজি ভেঙে দেয়।

প্রায়োরিটি কিউ সহ ডাইকস্ট্রার অ্যালগরিদম

import heapq

def dijkstra(graph, src):
    """
    graph: dict of {u: [(v, weight), ...]}
    Returns dist[] — shortest distances from src to all other nodes.
    """
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:   # stale entry — skip
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8)],
    'D': []
}
dist = dijkstra(graph, 'A')
for node, d in sorted(dist.items()):
    print(f"A -> {node}: {d}")