Dijkstra's Algorithm — Weighted Graph ပေါ်က Shortest Path

နားလည်ထားရမယ့် အချက်

BFS က edge ရေတွက်ပြီး shortest path ရှာတယ် — edge တိုင်းက 'step' တစ်ခုတည်း cost တူတယ်လို့ implicit assume လုပ်ထားတယ်။ Edge တွေက weight မတူတော့တဲ့အခါ — lesson တစ်ခုကနေတစ်ခု transition တစ်ခုက ၅ မိနစ်၊ နောက်တစ်ခုက ၃၀ မိနစ်ကုန်တယ်ဆိုရင် — ဒီ assumption ကျိုးပဲ့သွားတယ်: hop ပိုများတဲ့ path တစ်ခုက hop နည်းတဲ့ path ထက် legitimately ပိုစျေးသက်နိုင်တယ်။ Dijkstra's algorithm က ဒီ case အတွက် BFS ကို generalize လုပ်ပေးတယ် — plain queue အစား min-heap priority queue သုံးတယ်။ Node တိုင်းအတွက် လက်ရှိသိထားတဲ့ shortest distance ကို ထိန်းသိမ်းထားတယ် (start အတွက် 0၊ ကျန်တာ infinity ကနေစ) ပြီး heap ထဲက distance အငယ်ဆုံး node ကို ထုတ်ခါထုတ်ခါ pop လုပ်တယ် — greedy insight ကတော့ pop ပြီးသွားရင် ဒီ node ရဲ့ distance က final ဖြစ်ပြီဆိုတာပါ၊ ဘာလို့ဆိုတော့ ၎င်းဆီ ရောက်နိုင်တဲ့ path တခြားက distance ညီမျှ/ပိုကြီးတဲ့ node တစ်ခုကို ဖြတ်ရမှာမို့ ငယ်တဲ့ result ထုတ်လို့မရနိုင်လို့ပါ။ ပြီးရင် neighbor တစ်ခုချင်းစီကို relax လုပ်တယ် — လက်ရှိ node ကနေ neighbor ဆီရောက်တာက ယခင်သိထားတဲ့ distance ထက်ကောင်းရင် update လုပ်ပြီး distance အသစ်ကို heap ထဲ push ပြန်လုပ်တယ်။ ဒီ greedy 'frontier node စျေးအသက်ဆုံးကို အမြဲ expand လုပ်မယ်' strategy က negative edge weight ရှိရင် လုံးဝ ပျက်စီးသွားတယ်၊ ဘာလို့ဆိုတော့ negative edge တစ်ခုက final လို့ ယူထားပြီးသား distance ကို နောက်ပိုင်း ပိုငယ်အောင် ဆွဲချနိုင်လို့ပါ — ဒီ case ကို ကုန်ကျစရိတ်ပိုမြင့်ပေမယ့် ကိုင်တွယ်ဖို့ Bellman-Ford ဆိုတာ ရှိတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform က lesson တစ်ခုကနေတစ်ခု transition တစ်ခုစီကို weight တစ်ခုနဲ့ model လုပ်နိုင်တယ် — next lesson ပြီးဖို့ estimated minutes ဒါမှမဟုတ် difficulty jump penalty ဆိုပါစို့ — ဒါက 'learner ရဲ့ current level ကနေ goal lesson ဆီ best learning path ရှာတာ' ကို hop နည်းရင် အမြဲကောင်းချင်မှ ကောင်းမယ့် shortest-path problem အဖြစ် ပြောင်းပေးတယ်။ ဒီ weighted lesson graph ပေါ်က Dijkstra's algorithm က total estimated time ဒါမှမဟုတ် difficulty-adjusted cost အနည်းဆုံးဖြစ်တဲ့ path ကို ရှာပေးတယ် — edge count ပဲ ကြည့်ပေးနိုင်တဲ့ plain BFS ထက် ပိုကောင်းတယ်။ Platform က hop count ထက် ပိုအဓိပ္ပာယ်ရှိတဲ့ (goal ရောက်ဖို့ study time စုစုပေါင်းလိုမျိုး) တစ်ခုခုကို optimize လုပ်ချင်လာတဲ့အခါ plain BFS-based related-lessons traversal ကနေ natural upgrade ဖြစ်တယ်။

• BFS က edge weight တူတယ်လို့ assume လုပ်တယ် — edge weight မတူတော့ရင် Dijkstra လိုအပ်တယ်။
• Dijkstra က min-heap priority queue သုံးပြီး distance အသိအမှန်ဆုံး/အငယ်ဆုံးရှိတဲ့ node ကို အမြဲ ဦးစွာ expand လုပ်တယ်။
• Dijkstra က negative edge weight ရှိရင် အလုပ်မလုပ်ဘူး — အဲဒီ case အတွက် Bellman-Ford ရှိတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

import heapq

# weighted adjacency list: lesson -> [(neighbor, minutes_to_complete), ...]
graph = {
    "start": [("basics", 5), ("loops", 9)],
    "basics": [("loops", 2), ("functions", 6)],
    "loops": [("functions", 1), ("goal", 8)],
    "functions": [("goal", 3)],
    "goal": [],
}

def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue  # stale entry, a shorter path was already found
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

print(dijkstra(graph, "start"))

{'start': 0, 'basics': 5, 'loops': 7, 'functions': 8, 'goal': 11} ဟု node တိုင်းအတွက် start ကနေ shortest distance dictionary ကို print ထုတ်မည်။

Wikipedia — Dijkstra's algorithm — Data Structures & Algorithms