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

বেলম্যান-ফোর্ড এবং এসপিএফএ (Bellman-Ford & SPFA)

নেগেটিভ ওয়েটগুলো হ্যান্ডেল করুন এবং নেগেটিভ সাইকেল ধরে ফেলুন
Bellman-Ford:\(O(VE)\)SPFA average:\(O(kE)\)negative cycle:V−1 রাউন্ডের পরে যদি দূরত্ব আপডেট হয়, তবে ধরা পড়ে

একটি মুদ্রা বিনিময় বা কারেন্সি এক্সচেঞ্জ (currency exchange)-এর দামের বোর্ডের কথা চিন্তা করুন। বোর্ডের প্রতিটি সারি আপনাকে এক শহর থেকে অন্য শহরে যাওয়ার বর্তমান খরচ দেখায়। আপনি প্রতিদিন সকালে গিয়ে চেক করেন: "আমি যদি অন্য কোনো শহর হয়ে ঘুরে যাই, তাহলে কি কোনো রুটে আমার খরচ আরও কমবে?" যতক্ষণ পর্যন্ত আর কোনো উন্নতি বা খরচ কমানো সম্ভব না হয়, ততক্ষণ পর্যন্ত আপনি বোর্ডটি প্রতিনিয়ত আপডেট করতে থাকেন।

এটাই হলো মূলত বেলম্যান-ফোর্ড (Bellman-Ford)। ডাইকস্ট্রার (Dijkstra) মতো এটি সব দাম বা দূরত্ব পজিটিভ বলে ধরে নেয় না — এটি অনায়াসেই নেগেটিভ এজ ওয়েট (negative edge weights) সামলাতে পারে। এমনকি এটি এমন অস্বাভাবিক বা প্যাথলজিকাল (pathological) অবস্থা ধরতে পারে যেখানে দাম নেগেটিভ ইনফিনিটির দিকে সর্পিলাকারে বা স্পাইরাল (spiral) হতে থাকে (যাকে একটি নেগেটিভ সাইকেল বা negative cycle বলা হয়)।

অ্যালগরিদম: রিল্যাক্সেশনের V−1 রাউন্ড

শুরুতে: dist[source] = 0 ইনিশিয়ালাইজ বা নির্ধারণ করুন, আর বাকি অন্য সমস্ত দূরত্ব ধরুন = ∞। এরপর এটি V−1 বার পুনরাবৃত্তি বা রিপিট করুন:

গ্রাফের প্রতিটি এজের (u, v, w) জন্য চেক করে দেখুন: যদি dist[u] + w < dist[v] হয়, তবে dist[v] = dist[u] + w দিয়ে আপডেট করুন।

V−1 রাউন্ড কেন? V-ভার্টেক্স গ্রাফের যেকোনো সাধারণ বা সাধারণ পাথ বা পথে সর্বোচ্চ V−1 টি এজ থাকতে পারে। রিল্যাক্সেশনের বা চেক করার প্রতিটি রাউন্ড শর্টেস্ট পাত বা ক্ষুদ্রতম পথের আরও একটি এজকে "সক্রিয় বা অ্যাক্টিভেট" করতে পারে। সুতরাং V−1 রাউন্ডের পর, সমস্ত সহজ শর্টেস্ট পথগুলো সম্পূর্ণরূপে হিসাব করা হয়ে যায় — তবে শর্ত থাকে যে, সেখানে কোনো নেগেটিভ সাইকেল থাকতে পারবে না।

নেগেটিভ সাইকেল বা নেতিবাচক চক্র শনাক্তকরণ

V−1 রাউন্ড শেষ হওয়ার পর, আরো একটি রাউন্ড রান করুন। যদি কোনো দূরত্ব এখনও কমে যায়, এর মানে হলো সোর্স থেকে একটি নেগেটিভ সাইকেল বা নেতিবাচক চক্রে পৌঁছানো যাচ্ছে। কিন্তু কেন? নেগেটিভ সাইকেল নেই এমন গ্রাফে, শর্টেস্ট পাথগুলো সাধারণ পাথ হয় — যা V−1 রাউন্ড আগেই খুঁজে বের করতে পারে। এরপর এর আর কোনো উন্নতি বা খরচ কমার মানে হলো অ্যালগরিদমটি এমন একটি নেগেটিভ সাইকেলের মধ্যে ঘুরপাক খাচ্ছে, যা প্রতিবার চক্কর দেওয়ার সাথে সাথে মোট খরচ কমিয়ে দিচ্ছে।

নেগেটিভ সাইকেলের কারণে শর্টেস্ট পথ খুঁজে পাওয়া অসম্ভব হয়ে দাঁড়ায়: আপনি চাইলে চক্রটিকে বারবার ঘুরিয়ে মোট খরচকে আপনার ইচ্ছেমতো নেগেটিভের দিকে নিয়ে যেতে পারেন। মূলত এই বিশেষ অবস্থাটি শনাক্ত করার জন্যই বেলম্যান-ফোর্ড হলো সবচেয়ে পরিচিত এবং গ্রহণযোগ্য অ্যালগরিদম।

এসপিএফএ (Shortest Path Faster Algorithm বা SPFA)

বেলম্যান-ফোর্ড অ্যালগরিদম তার প্রতিটি রাউন্ডেই এমন কিছু ভার্টেক্সের এজগুলোকে রিল্যাক্স করে বা চেক করে সময় নষ্ট করে যাদের দূরত্ব আসলে পরিবর্তনই হয়নি। SPFA এই সমস্যাটি ঠিক করতে একটি কিউ (queue) ব্যবহার করে: এটি কেবল সেই সমস্ত ভার্টেক্সগুলোকেই নির্দিষ্ট কিউ-তে পাঠায় যাদের দূরত্ব সদ্য উন্নত বা আপডেট হয়েছে, এবং এটি শুধুমাত্র তাদের আউটগোয়িং (outgoing) বা বহির্গামী এজগুলোকেই রিল্যাক্স করে।

বাস্তব ক্ষেত্রে, SPFA কাজ করে \(O(kE)\) সময়ে, যেখানে সাধারণ গ্রাফগুলোর ক্ষেত্রে k ≈ 2 হয় — যা বেলম্যান-ফোর্ডের \(O(VE)\) এর চেয়ে অনেক দ্রুতগতিসম্পন্ন। কিন্তু কিছু প্রতিকূল ইনপুটের (adversarial inputs) কারণে এটি আবারও অবনতি লাভ করে \(O(VE)\)-তে ফিরে যেতে পারে, তাই কম্পিটিটিভ প্রোগ্রামিং (competitive programming) এর ক্ষেত্রে একে একটু সাবধানে ব্যবহার করতে হয়। নেগেটিভ সাইকেল শনাক্তকরণের জন্য, SPFA ট্র্যাক করে দেখতে পারে যে প্রতিটি ভার্টেক্সকে কতবার কিউ-তে বা এনকিউ (enqueue) করা হয়েছে — যদি কোনা একটি ভার্টেক্সকে কিউ-তে V বার এনকিউ করা হয়, তার মানে বুঝতে হবে সেখানে একটি নেগেটিভ সাইকেল বা নেতিবাচক চক্র রয়েছে।

ক্লাসিক একটি প্রয়োগ (Classic Application): কারেন্সি আরবিট্রেজ (Currency Arbitrage)

ধরুন প্রতিটি কারেন্সি বা মুদ্রাকে এক একটি ভার্টেক্স হিসেবে ধরা হলো, আর তাদের এক্সচেঞ্জ রেট বা বিনিময় হারকে −log(rate) ওয়েটসহ ডিরেক্টেড এজ (directed edges) হিসেবে। এই গ্রাফে একটি নেগেটিভ সাইকেল থাকার মানে হলো সাইকেলের চারপাশের বিনিময় হার গুণ করলে এর প্রাপ্ত ফলাফল বা গুণফল ১ (1) এর চেয়ে বেশি হবে — অর্থাৎ এটি একটি লাভজনক আরবিট্রেজ লুপ (arbitrage loop)। বেলম্যান-ফোর্ড ঠিক এই পরিস্থিতিটিই নিখুঁতভাবে শনাক্ত করতে পারে।

Click chart to zoom
বেলম্যান-ফোর্ড: V−1 বার রিল্যাক্সেশন রাউন্ড চলার পর একটি নেগেটিভ-সাইকেল চেক করা হয়
দ্রষ্টব্য: ডাইকস্ট্রা (Dijkstra) প্রতিটি ভার্টেক্সকে একদম চূড়ান্ত করে ফেলে এবং কখনোই আর সেখানে ফিরে যায় না। অন্যদিকে বেলম্যান-ফোর্ড প্রতিটি এজকে V−1 বার রিল্যাক্স বা চেক করে — যদিও এটি ধীরগতির, তবে নেগেটিভ ওয়েটের ক্ষেত্রে এটি সম্পূর্ণ নির্ভুল। আপনি বেলম্যান-ফোর্ডকে একজন নিরাপদ, নিবিড় প্রুফরিডার হিসেবে ভাবতে পারেন যেখানে ডাইকস্ট্রাকে মনে করতে পারেন একটি স্পিডি বা দ্রুতগামী অপ্টিমিস্টিক (optimistic) জিপিএস (GPS) হিসেবে।

নেগেটিভ সাইকেল শনাক্তকরণসহ বেলম্যান-ফোর্ড

def bellman_ford(n, edges, src):
    """
    n: number of vertices
    edges: list of (u, v, weight)
    Returns (dist, has_negative_cycle)
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0


    # V-1 relaxation rounds
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # early exit if stable


    # V-th round: check for negative cycle
    has_neg_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_neg_cycle = True
            break


    return dist, has_neg_cycle


# Graph: 0->1 (weight 6), 0->2 (7), 1->3 (-4), 2->1 (8), 3->0 (2)
edges = [(0,1,6),(0,2,7),(1,3,-4),(2,1,8),(3,0,2)]
dist, cycle = bellman_ford(4, edges, 0)
print(dist)   # [0, 2, 7, -2]
print(cycle)  # False


# Negative cycle example
edges2 = [(0,1,1),(1,2,-3),(2,0,1)]
_, cycle2 = bellman_ford(3, edges2, 0)
print(cycle2)  # True
Output
[0, 2, 7, -2]
False
True

Complexity

🐢 বেলম্যান-ফোর্ড (Bellman-Ford)
V−1 রাউন্ড × প্রতি রাউন্ডে E সংখ্যক এজ; মাঝারি সাইজের বা আকারের গ্রাফের জন্য বেশ কার্যকর
পলিনোমিয়াল (Polynomial) কিন্তু ধীরগতির \(O(VE)\)
⚡ এসপিএফএ (SPFA) (গড় ক্ষেত্র বা অ্যাভারেজ কেস)
কিউ-ভিত্তিক (Queue-based); শুধুমাত্র যে ভার্টেক্সগুলো নিয়ে সম্প্রতি আপডেট কাজ সম্পন্ন হয়েছে তাদেরকেই রিল্যাক্স করে — তবে এর সবচেয়ে খারাপ বা ওয়ার্স্ট কেস (worst case) এখনও \(O(VE)\) ই রয়ে যায়
সাধারণ বা প্র্যাকটিক্যাল কাজে অনেক বেশি দ্রুতগতির \(O(kE)\), k ≈ 2
🔍 নেগেটিভ সাইকেল বা নেতিবাচক চক্র শনাক্তকরণ
V-রাউন্ডে কোনো উন্নতি বা খরচ কমার মানে হলো একটি পৌঁছানো যায় এমন নেগেটিভ সাইকেল (negative cycle) বিদ্যমান
V−1 এর পরে একটি অতিরিক্ত রাউন্ড \(O(E)\)
📊 বনাম ডাইকস্ট্রা (vs Dijkstra)
যখন সমস্ত ওয়েট বা দূরত্ব পজিটিভ হয় তখন ডাইকস্ট্রা ব্যবহার করুন; অন্যথায় বেলম্যান-ফোর্ড (Bellman-Ford)
ধীরগতির, তবে নেগেটিভ ওয়েটের (negative weights) এজ সামলাতে পারে \(O(VE)\) বনাম \(O((V+E)\) log V)

ছোট কুইজ

বেলম্যান-ফোর্ড ঠিক V−1 বার রিল্যাক্সেশন রাউন্ড কেন রান করে বা ঘোরে?

পড়া চালিয়ে যান