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

ফ্লয়েড-ওয়ার্শল অ্যালগরিদম (Floyd-Warshall)

এক চক্করে প্রতিটি শহরের জোড়ার মধ্যে সবচেয়ে ছোট পথ খুঁজে বের করুন
time:O(V³)space:O(V²)handles:নেগেটিভ ওয়েট (নেগেটিভ সাইকেল নয়)

ধরুন আপনি একটি এয়ারলাইন চালান এবং আপনি প্রতিটি শহরের জোড়ার (pair) মধ্যে সবচেয়ে সস্তা ভাড়া জানতে চান। আপনি প্রতিটি শহর থেকে ডাইকস্ট্রার অ্যালগরিদম চালাতে পারেন, তবে এর চেয়ে আরও একটি সুন্দর উপায় আছে: প্রতিটি শহরের জন্য জিজ্ঞাসা করুন, "K শহরের ওপর দিয়ে উড়ে গেলে কি কোনো ট্রিপ সস্তা হয়?"

সরাসরি ফ্লাইটের দাম দিয়ে শুরু করুন। তারপর জিজ্ঞাসা করুন: "১ নম্বর শহরের ওপর দিয়ে গেলে কি কোনো ট্রিপ সস্তা হয়?" দামগুলো আপডেট করুন। তারপর: "২ নম্বর শহরের ওপর দিয়ে গেলে কি কোনো ট্রিপ সস্তা হয়?" আবার আপডেট করুন। প্রতিটি শহরকে একটি সম্ভাব্য লেওভার (layover) বা যাত্রাবিরতি হিসেবে বিবেচনা করার পর, আপনার প্রাইস টেবিলের প্রতিটি এন্ট্রিই হবে প্রকৃত সবচেয়ে সস্তা ভাড়া।

এটাই হলো ফ্লয়েড-ওয়ার্শল (Floyd-Warshall) — একটি চমৎকার সাধারণ ডাইনামিক প্রোগ্রামিং (DP) ধারণার ওপর নির্মিত শর্টেস্ট-পাথ অ্যালগরিদম যা সব জোড়ার (all-pairs) জন্য কাজ করে।

ডিপি ফর্মুলেশন (The DP Formulation)

dist[i][j] কে i থেকে j পর্যন্ত সবচেয়ে ছোট পথ হিসাবে ধরে নিন। প্রাথমিকভাবে:

  • যদি সরাসরি কোনো এজ বা পথ থাকে, তবে dist[i][j] = weight(i,j)
  • dist[i][i] = 0
  • অন্যথায় dist[i][j] = ∞

মূল রিকারেন্স (recurrence) — 1 থেকে V পর্যন্ত প্রতিটি মধ্যবর্তী ভার্টেক্স (intermediate vertex) k এর জন্য লুপ চালান:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

সহজ কথায়: "k এর ওপর দিয়ে i থেকে j তে পৌঁছানো কি আমাদের এপর্যন্ত পাওয়া যেকোনো রুটের চেয়ে সস্তা?" আউটার লুপ (outer loop) k এর সমস্ত V মান শেষ করার পর, প্রতিটি জোড়া (i, j) গ্লোবালি অপ্টিমাল (globally optimal) বা সর্বোত্তম উত্তর ধারণ করে।

কেন ইন-প্লেস আপডেট করা নিরাপদ (Why In-Place Updates Are Safe)

3D ফর্মুলেশন dp[k][i][j] কে একটি 2D অ্যারে-তে সংকুচিত করা যায়। আপনি কেন ইন-প্লেস আপডেট করতে পারেন? যখন মধ্যবর্তী ভার্টেক্স k প্রসেস করা হয়, তখন dist[i][k] এবং dist[k][j] এর মানগুলো k-তম ইটারেশনে পরিবর্তন হয় না — এগুলো এমন পথগুলোকে নির্দেশ করে যা মধ্যবর্তী হিসেবে {1..k−1} ব্যবহার করে, যা আগে থেকেই অপ্টিমাল বা সর্বোত্তম এবং এগুলো মধ্যবর্তী হিসেবে k-কে ব্যবহার করে না (k-এ যাওয়ার জন্য k-এর ভেতর দিয়ে গেলে কেবল খরচই বাড়বে)। তাই এই মানগুলো ব্যবহার করে ইন-প্লেস dist[i][j] আপডেট করা সবসময়ই সঠিক।

নেগেটিভ সাইকেল শনাক্ত করা (Detecting Negative Cycles)

ফ্লয়েড-ওয়ার্শল চালানোর পর, ডায়াগোনাল বা কর্ণ বরাবর চেক করুন। যদি কোনো ভার্টেক্স i এর জন্য dist[i][i] < 0 হয়, তবে i এর ভেতর দিয়ে যাওয়া একটি নেগেটিভ সাইকেল রয়েছে। i থেকে i তে যাওয়ার একটি তুচ্ছ বা খালি পথের খরচ 0; যদি এটি নেগেটিভ হয়ে যায়, এর মানে অ্যালগরিদমটি এমন একটি সাইকেল পেয়েছে যার মোট ওয়েট নেগেটিভ। নেগেটিভ সাইকেলের ভেতর দিয়ে যায় এমন যেকোনো ক্ষুদ্রতম পথ আনডিফাইন্ড (undefined) বা অসংজ্ঞায়িত (অসীমভাবে সস্তা)।

ট্রানজিটিভ ক্লোজার (Transitive Closure)

min/+ এর বদলে OR/AND (বুলিয়ান মান ব্যবহার করে) প্রতিস্থাপন করে প্রতিটি জোড়া (i, j) একে অপরের সাথে যুক্ত কি না তা গণনা করুন। এই ট্রানজিটিভ ক্লোজার (transitive closure) পদ্ধতিটি O(V³) সময়ে কাজ করে এবং এক চক্করেই সব জোড়ার জন্য রিচেবিলিটি কোয়েরির (reachability queries) উত্তর দেয়।

কখন ফ্লয়েড-ওয়ার্শল বনাম ডাইকস্ট্রা ব্যবহার করবেন

একটি ডেনস গ্রাফে (dense graph) (E ≈ V²) সমস্ত জোড়ার শর্টেস্ট পাথে বা নেগেটিভ ওয়েট থাকলে, সাধারণত ফ্লয়েড-ওয়ার্শলের O(V³) বড় সুবিধা দেয়। শুধুমাত্র পজিটিভ ওয়েট-যুক্ত একটি স্পার্স গ্রাফে (sparse graph), প্রতিটি সোর্স থেকে ডাইকস্ট্রা চালালে তা O(V · (V+E) log V) সময় নেয়, যা অনেক ভালো হতে পারে। সাধারণত যখন E ≪ V² হয় তখন ডাইকস্ট্রা ভালো কাজ করে।

দ্রষ্টব্য: তিনটি নেস্টেড ফর-লুপ থাকে — k, তারপর i, তারপর j। আউটার লুপ k হলো মধ্যবর্তী শহর। এর ক্রমটি খুবই গুরুত্বপূর্ণ: k কে অবশ্যই সবার বাইরে রাখতে হবে। যদি আপনি ভুল করে k ভেতরে রাখেন, তবে আপনি ভুল উত্তর পাবেন।

ফ্লয়েড-ওয়ার্শল সমস্ত-জোড়ার শর্টেস্ট পাথ

def floyd_warshall(n, edges):
    """
    n: number of vertices (0-indexed)
    edges: list of (u, v, weight)
    Returns dist[i][j] = shortest path from i to j, or None if negative cycle.
    """
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)


    for k in range(n):           # intermediate vertex
        for i in range(n):       # source
            for j in range(n):   # destination
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]


    # Check for negative cycles
    for i in range(n):
        if dist[i][i] < 0:
            return None  # negative cycle
    return dist


# 4 cities, 0-indexed
edges = [(0,1,3),(0,3,7),(1,0,8),(1,2,2),(2,0,5),(2,3,1),(3,0,2)]
dist = floyd_warshall(4, edges)
for i in range(4):
    for j in range(4):
        val = dist[i][j] if dist[i][j] != float('inf') else '∞'
        print(f"{i}->{j}: {val}", end='  ')
    print()
Output
0->0: 0  0->1: 3  0->2: 5  0->3: 6  
1->0: 7  1->1: 0  1->2: 2  1->3: 3  
2->0: 5  2->1: 8  2->2: 0  2->3: 1  
3->0: 2  3->1: 5  3->2: 7  3->3: 0

Complexity

✈️ সমস্ত জোড়ার শর্টেস্ট পাথ (All-pairs shortest path)
k, i, j এর ওপর তিনটি নেস্টেড লুপ — V এর মান ~1000 পর্যন্ত হলে এটি ব্যবহারিক
ভার্টেক্স সংখ্যার সাপেক্ষে কিউবিক (Cubic) O(V³)
💾 মেমরি বা স্পেস
প্রতিটি জোড়ার জন্য একটি করে দূরত্ব; স্পেস অপটিমাইজেশনের পর 2D অ্যারেই যথেষ্ট
ভার্টেক্স সংখ্যার সাপেক্ষে স্কোয়ার বা দ্বিঘাত (Quadratic) O(V²)
🔍 নেগেটিভ সাইকেল শনাক্তকরণ
যদি কোনো i এর জন্য dist[i][i] < 0 হয়, তবে i এর ভেতর দিয়ে একটি নেগেটিভ সাইকেল রয়েছে
বিনামূল্যে — প্রধান লুপের পর চেক করুন O(V)
🆚 ডাইকস্ট্রা × V সোর্স (স্পার্স গ্রাফে)
স্পার্স নন-নেগেটিভ গ্রাফের ক্ষেত্রে, প্রতিটি ভার্টেক্স থেকে ডাইকস্ট্রা চালানো ফ্লয়েড-ওয়ার্শলের চেয়ে ভালো ফলাফল দেয়
প্রায়শই স্পার্স গ্রাফের জন্য দ্রুততর O(V·(V+E) log V)

ছোট কুইজ

ফ্লয়েড-ওয়ার্শল সম্পূর্ণ হওয়ার পর dist[i][j] কী নির্দেশ করে?

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