အခန်း ၁၉ - Advanced Graph Algorithms

အခန်း ၁၈ မှာ graph တစ်ခုအတွင်းမှာ ရှိတဲ့ vertex တွေကို စနစ်တကျ လှည့်ပတ်ရှာဖွေတဲ့ (traversal) နည်းလမ်းတွေဖြစ်တဲ့ BFS (Breadth-First Search) နဲ့ DFS (Depth-First Search) အကြောင်းကို အသေးစိတ် လေ့လာခဲ့ကြပြီး ဖြစ်ပါတယ်။ ဒါပေမယ့် တကယ့် လက်တွေ့ ကမ္ဘာ (real-world) ပြဿနာတွေမှာ "vertex တွေ တစ်ခုနဲ့တစ်ခု ဆက်နေသလား" ဆိုတာထက် ပိုမို ရှုပ်ထွေးပြီး နက်နဲတဲ့ မေးခွန်းတွေကို ဖြေရှင်းဖို့ လိုအပ်လာပါတယ်။

ဥပမာအားဖြင့် —

• Dependency Ordering: "Software package တွေ၊ သို့မဟုတ် task တွေကို install လုပ်တဲ့အခါ ဘယ်အရာကို အရင်လုပ်ပြီး ဘယ်အရာကို နောက်မှ လုပ်ရမလဲ"
• Weighted Shortest Path: "မြို့ A ကနေ မြို့ B ကို သွားတဲ့အခါ ခရီးအကွာအဝေး သို့မဟုတ် သွားလာစရိတ် အသက်သာဆုံး လမ်းကြောင်းကို ဘယ်လို ရှာမလဲ"
• Minimum Spanning Tree: "မြို့ နှစ်မြို့ကို လျှပ်စစ်ဓါတ်အားလိုင်း သို့မဟုတ် ဖုန်းလိုင်းတွေ ချိတ်ဆက်တဲ့အခါ ကုန်ကျစရိတ် အနည်းဆုံးဖြစ်အောင် ဘယ်လို ချိတ်ဆက်မလဲ"

ဒီအခန်းမှာတော့ real-world developer တစ်ယောက်အနေနဲ့ နေ့စဉ် ကြုံတွေ့ရလေ့ရှိတဲ့ အရေးပါဆုံး Graph Algorithm တွေကို အခြေခံမှစ၍ လက်တွေ့ကျကျ ရှင်းပြသွားပါမယ်။ Algorithm တစ်ခုစီအတွက် ၎င်းတို့ ဖြေရှင်းပေးသည့် ပြဿနာ၊ အလုပ်လုပ်ပုံ သဘောတရား (Intuition)၊ တစ်ဆင့်ချင်း လုပ်ဆောင်ပုံ (Step trace)၊ Code implementations နှင့် Time/Space complexity တွေကို အသေးစိတ် လေ့လာသွားကြပါမယ်။

ဒီအခန်းမှာ လေ့လာသွားမယ့် အဓိက Algorithm များနှင့် ၎င်းတို့၏ အဓိက သဘောတရားများမှာ အောက်ပါအတိုင်း ဖြစ်ပါတယ် —

Topological Sort — Dependency Ordering

အခြေခံ သဘောတရားနှင့် အသုံးဝင်ပုံ

Topological Sort ဆိုတာ Directed Acyclic Graph (DAG) — ဆိုလိုတာက ဦးတည်ချက်ရှိပြီး cycle (ဝိုင်းပတ်မှု) မရှိတဲ့ graph တစ်ခုမှာ vertex တွေရဲ့ "ဘယ်အရာက အရင်၊ ဘယ်အရာက နောက်" ဆိုတဲ့ တရားဝင် လုပ်ဆောင်မှု အစီအစဉ် (valid ordering) ကို ရှာဖွေပေးတဲ့ algorithm ဖြစ်ပါတယ်။

graph ထဲမှာ directed edge A → B ရှိနေတယ်ဆိုရင် "B ကို မလုပ်ခင် A ကို အရင်ပြီးအောင် လုပ်ရမယ်" (A ပြီးမှ B) လို့ အဓိပ္ပါယ်ရပါတယ်။ ဒါကြောင့် Topological Sort ဖြင့် ထွက်လာတဲ့ အစီအစဉ်မှာ node A ဟာ node B ရဲ့ အရှေ့မှာ အမြဲတမ်း ရောက်ရှိနေရပါမယ်။

   package dependency ဥပမာ:
      (A) ──┐
            ├──▶ (C) ──▶ (D)
      (B) ──┘

   - C ကို သုံးဖို့ A နဲ့ B အရင်လိုအပ်တယ်။
   - D ကို သုံးဖို့ C အရင်လိုအပ်တယ်။
   
   တရားဝင်သော အစီအစဉ် (Valid Order):   A, B, C, D  (သို့မဟုတ်)  B, A, C, D
   မတရားဝင်သော အစီအစဉ် (Invalid Order): C, A, B, D  (C က A/B ရဲ့ အရှေ့ ရောက်နေ၍ မှားယွင်းသည်)

လက်တွေ့ ကမ္ဘာမှာ Software Package Management (npm, pip, maven) တွေမှာ package တွေ install လုပ်မယ့် အစီအစဉ် ရှာတာ၊ Build tools (Make, Bazel, Webpack) တွေမှာ source file တွေ compile လုပ်မယ့် အစီအစဉ် သတ်မှတ်တာ၊ တက္ကသိုလ် ဘာသာရပ် prerequisites တွေနဲ့ Task Scheduling ပြဿနာတွေမှာ Topological Sort ကို အဓိက သုံးကြပါတယ်။

အရေးကြီးသော အချက်: Topological Order ရရှိဖို့အတွက် Graph မှာ Cycle (ဝိုင်းပတ်မှု) လုံးဝ မရှိရပါ (DAG ဖြစ်ရပါမည်)။ အကယ်၍ "A ပြီးမှ B၊ B ပြီးမှ A" ဆိုပြီး Cycle ဖြစ်နေရင် circular dependency ဖြစ်ပေါ်နေတာ ကြောင့် ဘယ်ဟာကိုမှ စတင် လုပ်ဆောင်လို့ ရတော့မည် မဟုတ်ပါ။

Kahn's Algorithm (In-degree နည်းလမ်း)

Topological Sort ကို ရေးသားဖို့ အသုံးအများဆုံး နည်းလမ်းမှာ Kahn's Algorithm ဖြစ်ပြီး ၎င်းသည် In-degree သဘောတရားကို အခြေခံထားပါတယ်။

• In-degree: Vertex တစ်ခုဆီသို့ ဝင်ရောက်လာသော edge အရေအတွက် ဖြစ်ပါတယ်။ ဒါဟာ "ဒီ task ကို မလုပ်ခင် အရင်ပြီးအောင် လုပ်ရမယ့် prerequisite အရေအတွက်" ကို ဆိုလိုတာဖြစ်ပါတယ်။
• In-degree = 0: Prerequisite တစ်ခုမှ မရှိတော့တဲ့အတွက် ဒီ vertex ကို အခုချက်ချင်း စတင် လုပ်ဆောင်လို့ ရပြီ လို့ ဆိုလိုပါတယ်။

အလုပ်လုပ်ပုံ နည်းလမ်း:

1. Graph အတွင်းရှိ vertex အားလုံး၏ in-degree ကို စတင် တွက်ချက်ပါတယ်။
2. In-degree 0 ဖြစ်သော vertex တွေကို Queue ထဲသို့ ထည့်သွင်းပါတယ်။
3. Queue ထဲမှ vertex များကို တစ်ခုချင်းစီ ထုတ်ယူကာ topological order စာရင်းထဲသို့ ထည့်ပါတယ်။
4. ထုတ်ယူလိုက်သော vertex နှင့် ချိတ်ဆက်ထားသည့် အိမ်နီးချင်း vertex များ၏ in-degree ကို 1 လျှော့ပေးပါတယ်။ အကယ်၍ အိမ်နီးချင်း vertex ၏ in-degree သည် 0 ဖြစ်သွားပါက ၎င်းကို Queue ထဲသို့ ထပ်မံ ထည့်သွင်းပါတယ်။
5. Queue ဗလာ ဖြစ်သွားသည်အထိ ဒီလုပ်ငန်းစဉ်ကို ထပ်ခါထပ်ခါ လုပ်ဆောင်ပါတယ်။

အကယ်၍ Graph ထဲမှာ Cycle ရှိနေပါက Cycle ထဲတွင် ပါဝင်သော vertex များ၏ in-degree သည် ဘယ်တော့မှ 0 ဖြစ်လာမည် မဟုတ်ပါ။ ဒါကြောင့် ထွက်လာသော topological order ၏ ရလဒ် အရေအတွက်သည် စုစုပေါင်း vertex အရေအတွက် n ထက် နည်းနေပါလိမ့်မည်။ ဒါကိုကြည့်ပြီး Graph ထဲမှာ Cycle ရှိမရှိပါ တစ်ပါတည်း စစ်ဆေးနိုင်ပါတယ်။

Step-by-step Trace

အထက်ပါ ဥပမာ (A→C, B→C, C→D) ကို Kahn's Algorithm ဖြင့် စနစ်တကျ လိုက်ပါ ကြည့်ရအောင် —

   ၁။ In-degree များ စတင်တွက်ချက်ခြင်း:
      in-degree: A = 0, B = 0, C = 2, D = 1
      Queue: [A, B] (in-degree 0 ရှိသော A နှင့် B အား ထည့်ထားသည်)

   ၂။ Queue မှ A ကို ထုတ်ယူသည် (Order = [A]):
      - C ရဲ့ in-degree ကို 1 လျှော့သည် (C in-degree: 2 -> 1)

   ၃။ Queue မှ B ကို ထုတ်ယူသည် (Order = [A, B]):
      - C ရဲ့ in-degree ကို 1 ထပ်မံလျှော့သည် (C in-degree: 1 -> 0)
      - C ရဲ့ in-degree 0 ဖြစ်သွားပြီဖြစ်၍ C အား Queue ထဲသို့ ထည့်သည် (Queue = [C])

   ၄။ Queue မှ C ကို ထုတ်ယူသည် (Order = [A, B, C]):
      - D ရဲ့ in-degree ကို 1 လျှော့သည် (D in-degree: 1 -> 0)
      - D ရဲ့ in-degree 0 ဖြစ်သွားပြီဖြစ်၍ D အား Queue ထဲသို့ ထည့်သည် (Queue = [D])

   ၅။ Queue မှ D ကို ထုတ်ယူသည် (Order = [A, B, C, D]):
      - ဆက်လက် လုပ်ဆောင်စရာ Edge မရှိတော့ပါ။

   ရလဒ် အစီအစဉ်: [A, B, C, D] ( size = 4 == n ဖြစ်၍ Cycle မရှိပါ ✓ )

Java Implementation

import java.util.*;

public class TopologicalSort {
    public List<Integer> topoSort(int n, List<List<Integer>> graph) {
        int[] indegree = new int[n];
        // Vertex တစ်ခုစီ၏ in-degree ကို စတင်တွက်ချက်ခြင်း
        for (int u = 0; u < n; u++) {
            for (int v : graph.get(u)) {
                indegree[v]++;
            }
        }

        // In-degree 0 ရှိသော vertex များကို Queue ထဲသို့ ထည့်ခြင်း
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);

            // အိမ်နီးချင်း vertex များ၏ in-degree ကို လျှော့ချခြင်း
            for (int next : graph.get(node)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // ရလဒ်အရွယ်အစား n နှင့် တူညီပါက valid order ဖြစ်သည်၊ မတူပါက cycle ရှိနေသည်
        return order.size() == n ? order : new ArrayList<>();
    }
}

Complexity Analysis:

• Time Complexity: $O(V + E)$ — Vertex နှင့် Edge တစ်ခုစီကို တစ်ကြိမ်စီသာ ဖြတ်သန်း ကြည့်ရှု သောကြောင့် ဖြစ်ပါတယ်။
• Space Complexity: $O(V + E)$ — Adjacency list၊ In-degree array နှင့် Queue အတွက် နေရာယူ သောကြောင့် ဖြစ်ပါတယ်။

Dijkstra's Algorithm — Weighted Shortest Path

အခြေခံ သဘောတရားနှင့် Greedy Logic

အခန်း ၁၈ ၌ လေ့လာခဲ့သော BFS သည် edge တွေမှာ အလေးချိန် (weight) မရှိသည့် unweighted graph များတွင် အတိုဆုံး လမ်းကြောင်း (shortest path) ကို ရှာဖွေပေးနိုင်ခဲ့ပါတယ်။ သို့သော်လည်း တကယ့် လက်တွေ့ မြေပုံများတွင် လမ်းကြောင်း တစ်ခုစီ၏ အကွာအဝေး၊ သို့မဟုတ် တန်ဖိုး (edge weight) များသည် မတူညီကြပါ။ ဒီလို weighted graph များတွင် Single-Source Shortest Path (စတင်မှတ် တစ်ခုမှ ကျန် vertex အားလုံးသို့ အတိုဆုံး လမ်းကြောင်း) ရှာဖွေဖို့ရာ Dijkstra's Algorithm ကို သုံးစွဲကြပါတယ်။

graph TD
    A((A))
    B((B))
    C((C))
    D((D))
    A ---|4| B
    A ---|1| C
    A ---|2| D
    C ---|5| D
    D ---|5| B

• A မှ C သို့ တိုက်ရိုက်: 1
• A မှ B သို့ တိုက်ရိုက်: 4 (သို့သော် A -> C -> D -> B ကဲ့သို့ ပိုမို သက်သာသော လမ်းကြောင်း ရှိနိုင်ပါသလား)

Dijkstra ၏ အဓိက Greedy သဘောတရား:
"စတင်မှတ် (Start node) မှ လက်ရှိ အကွာအဝေး အနည်းဆုံး (အသက်သာဆုံး) ရှိနေသည့် vertex ကို အမြဲတမ်း ပထမဦးစားပေး ရွေးချယ်ပြီး finalize လုပ်သွားခြင်း" ဖြစ်ပါတယ်။

ဒီ Greedy logic မှန်ကန်ဖို့အတွက် အရေးကြီးသော ကန့်သတ်ချက် တစ်ခုရှိပါတယ် — Graph အတွင်းရှိ Edge weight များသည် အနုတ်ကိန်း မဟုတ်ရပါ (Non-negative: edge weight ≥ 0)။ Edge weight များ အပေါင်းကိန်း သို့မဟုတ် ၀ ဖြစ်နေသမျှ ကာလပတ်လုံး၊ လက်ရှိ အတိုဆုံး ရောက်ရှိနေသော vertex ၏ distance ကို အခြား မည်သည့် လမ်းကြောင်းကမှ ထပ်မံ လျှော့ချပေးနိုင်တော့မည် မဟုတ်ပါ။ ( အကြောင်းမှာ မည်သည့် edge ကိုမဆို ထပ်မံ ကူးဖြတ်ပါက weight သည် တိုးလာရုံသာ ရှိပြီး လျော့ကျသွားမည် မဟုတ်သောကြောင့် ဖြစ်ပါသည် )။

အကွာအဝေး အနည်းဆုံး vertex ကို အမြန်ဆုံး ဆွဲထုတ်နိုင်ရန် Min-Heap (PriorityQueue) ကို သုံးစွဲကြပါတယ်။

Relaxation သဘောတရား

Shortest-path algorithm တွေရဲ့ အဓိက အနှစ်သာရမှာ Edge Relaxation ဖြစ်ပါတယ်။

   if (dist[u] + weight(u, v) < dist[v]) {
       dist[v] = dist[u] + weight(u, v);
   }

ဒါဟာ "Start မှ v သို့ လက်ရှိ သိထားသော အတိုဆုံး လမ်းကြောင်းထက်၊ u ကို ဖြတ်သန်းပြီးမှ v သို့ သွားသော လမ်းကြောင်းက ပိုမို တိုတောင်းပါက v ၏ အကွာအဝေး တန်ဖိုး (dist[v]) ကို အသစ် ပြင်ဆင် (update) မယ်" ဆိုတဲ့ သဘောတရား ဖြစ်ပါတယ်။

Step-by-step Trace

အထက်ပါ Graph တွင် A မှ စတင်၍ Dijkstra algorithm ဖြင့် အတိုဆုံး လမ်းကြောင်း ရှာပုံကို လိုက်ပါ ကြည့်ရအောင် —

   စတင်ချိန်: dist = {A: 0, B: ∞, C: ∞, D: ∞}, PriorityQueue = [(0, A)]

   ၁။ PQ မှ (0, A) ကို ထုတ်ယူသည် ( A အား Finalize လုပ်သည် ):
      - Edge A->B (weight 4): dist[B] = min(∞, 0 + 4) = 4  -> PQ ထဲသို့ (4, B) ထည့်သည်
      - Edge A->C (weight 1): dist[C] = min(∞, 0 + 1) = 1  -> PQ ထဲသို့ (1, C) ထည့်သည်
      - Edge A->D (weight 2): dist[D] = min(∞, 0 + 2) = 2  -> PQ ထဲသို့ (2, D) ထည့်သည်

   ၂။ PQ မှ အသေးဆုံး (1, C) ကို ထုတ်ယူသည် ( C အား Finalize လုပ်သည် ):
      - Edge C->D (weight 5): 1 + 5 = 6 ( သို့သော် dist[D] = 2 ဖြစ်ပြီးသား မို့ update မလုပ်ပါ )

   ၃။ PQ မှ အသေးဆုံး (2, D) ကို ထုတ်ယူသည် ( D အား Finalize လုပ်သည် ):
      - Edge D->B (weight 5): 2 + 5 = 7 ( သို့သော် dist[B] = 4 ဖြစ်ပြီးသား မို့ update မလုပ်ပါ )

   ၄။ PQ မှ (4, B) ကို ထုတ်ယူသည် ( B အား Finalize လုပ်သည် ):
      - ဆက်လက် လုပ်ဆောင်စရာ edge မရှိပါ။

   ရလဒ် အတိုဆုံး အကွာအဝေးများ: dist = {A: 0, B: 4, C: 1, D: 2}

Practical Problem: Network Delay Time

Node n ခု (1 မှ n အထိ) နှင့် ရောက်ရှိရန် ကြာမြင့်ချိန်များ ပါဝင်သော directed weighted edges times ([u, v, w] = u မှ v သို့ ရောက်ရန် w စက္ကန့်) ကို ပေးထားသည်။ စတင်မှတ် Node k မှ စတင်၍ ကွန်ရက်အတွင်းရှိ Node အားလုံး သို့ သတင်းအချက်အလက် (signal) ရောက်ရှိရန် စုစုပေါင်း ဘယ်နှစ် စက္ကန့် ကြာမြင့်မည်နည်း။ Node အားလုံးသို့ မရောက်ရှိနိုင်ပါက -1 ကို ပြန်ပေးပါ။

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
( Explanation: 2->1 သို့ 1s ကြာသည်၊ 2->3->4 သို့ 2s ကြာသည်။ signal သည် တစ်ပြိုင်နက် ပျံ့နှံ့သဖြင့် Node အားလုံး ရောက်ရန် အဝေးဆုံး Node ၏ အချိန်ဖြစ်သော 2s ကြာမြင့်မည် ဖြစ်သည် )

Java Solution

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Adjacency list ဆောက်လုပ်ခြင်း: u -> List of (v, w)
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] t : times) {
            graph[t[0]].add(new int[]{t[1], t[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        // Min-Heap: (distance, node) အလိုက် စီစဉ်ထားသည်
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];

            // ဟောင်းနွမ်းနေသော (ပိုမိုကြီးမားသော distance ရှိသော) entry အား ကျော်လွန်ခြင်း
            if (d > dist[u]) continue;

            for (int[] edge : graph[u]) {
                int v = edge[0], weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        // Node အားလုံးထဲတွင် အဝေးဆုံး ရောက်ရှိသည့် အချိန်အား ရှာဖွေခြင်း
        int maxDelay = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // မရောက်နိုင်သော node ရှိပါက -1
            maxDelay = Math.max(maxDelay, dist[i]);
        }
        return maxDelay;
    }
}

Complexity Analysis:

• Time Complexity: $O(E \log V)$ — Edge တစ်ခုစီသည် Min-Heap ထထဲသို့ ဝင်/ထွက် လုပ်ဆောင်ပြီး Min-Heap operation တိုင်းသည် $O(\log V)$ ကြာမြင့်သောကြောင့် ဖြစ်ပါတယ်။
• Space Complexity: $O(V + E)$ — Graph ကို Adjacency List ဖြင့် သိမ်းဆည်းခြင်းနှင့် Heap memory တို့အတွက် ဖြစ်ပါတယ်။

A* (A-star) Search — Goal-directed Pathfinding

Dijkstra နှင့် A* Search တို့၏ ကွာခြားချက်

Dijkstra's algorithm သည် စတင်မှတ်မှ ပတ်ဝန်းကျင် အရပ်ရပ်သို့ ရေလှိုင်းများ ပျံ့နှံ့သွားသကဲ့သို့ တညီတည်း ကျယ်ပြန့်စွာ ရှာဖွေသွားလေ့ ရှိပါတယ်။ ဒါဟာ "ပန်းတိုင် (Goal) က ဘယ်နေရာမှာ ရှိမှန်း မသိသေးတဲ့" ပြဿနာတွေမှာ သင့်တော်ပေမယ့်၊ မြေပုံပေါ်မှာ Goal ရဲ့ တည်နေရာကို ကြိုတင်သိရှိထားသည့် Grid သို့မဟုတ် Game Pathfinding ပြဿနာများတွင် အလဟဿ ရှာဖွေမှုများ ပိုမို များပြားစေပါတယ်။

A Search Algorithm* သည် Dijkstra ကို ပိုမို အဆင့်မြှင့်တင်ထားခြင်း ဖြစ်ပြီး၊ Node တစ်ခုကို ရွေးချယ်သည့်အခါ "စတင်မှတ်မှ လက်ရှိနေရာသို့ ကုန်ကျစရိတ်" တစ်ခုတည်းကို မကြည့်ဘပြင်၊ "ဒီနေရာမှ ပန်းတိုင်ဆီသို့ ဘယ်လောက် ကျန်ရှိဦးမည်နည်း" ဆိုသည့် ခန့်မှန်းချက် (Heuristic function) ကိုပါ ထည့်သွင်း တွက်ချက်ကာ Goal ရှိရာ ဘက်သို့ ဦးတည်၍ အမြန်ဆုံး ရှာဖွေပေးပါတယ်။

နှစ်ခုလုံးက Min-Heap + Relaxation အခြေခံပုံ တူပေမယ့်၊ Heap ထဲက Node တစ်ခုကို ရွေးတဲ့ priority value နဲ့ ရှာဖွေတဲ့ ဦးတည်ချက် ကသာ ကွာခြားပါတယ်။

အဓိက Insight: $h(n) = 0$ ထားလိုက်ရင် A* ဟာ Dijkstra အဖြစ်ပြန်ပြောင်းသွားပါတယ်။ ဒါကြောင့် Dijkstra က A* ၏ အထူးပြု (special case) တစ်ခုဟု မှတ်ယူနိုင်ပါတယ်။

$f(n) = g(n) + h(n)$ အဓိက ညီမျှခြင်း

A* Search တွင် Node တစ်ခုစီအတွက် တန်ဖိုး ၃ ခုကို စက်ဝိုင်းလည် တွက်ချက်ပါတယ်။

• $g(n)$: Start Node မှ လက်ရှိ Node n သို့ ရောက်ရှိရန် တကယ် ကုန်ကျခဲ့သည့် စရိတ် (Dijkstra ၏ dist တန်ဖိုး ဖြစ်သည်)။
• $h(n)$ (Heuristic): လက်ရှိ Node n မှ Goal Node သို့ ရောက်ရှိရန် ခန့်မှန်းခြေ ကုန်ကျမည့် စရိတ်။
• $f(n) = g(n) + h(n)$: လက်ရှိ Node n ကို ဖြတ်သန်းသွားပါက စုစုပေါင်း ကုန်ကျနိုင်မည့် ခန့်မှန်းစရိတ်။

Min-Heap ထဲတွင် $g(n)$ အစား $f(n)$ တန်ဖိုး အသေးဆုံး ရှိသော Node ကို ဦးစားပေး ဆွဲထုတ် လုပ်ဆောင်သောကြောင့် ပန်းတိုင်သို့ ထိရောက်စွာ အမြန်ဆုံး ရောက်ရှိစေပါတယ်။

Admissible Heuristic ဆိုတာဘာလဲ

A* Search မှ ပေးသော အဖြေသည် အတိုဆုံးနှင့် အမှန်ကန်ဆုံး (optimal) ဖြစ်စေရန်အတွက် Heuristic function $h(n)$ သည် Admissible ဖြစ်ရပါမည်။ Admissible ဖြစ်တယ်ဆိုသည်မှာ ခန့်မှန်းချက် $h(n)$ သည် တကယ့် အကွာအဝေးထက် မည်သည့်အခါမျှ ပိုမို မကြီးမားရပါ (Never overestimate)။

2D Grid Pathfinding များတွင် အသုံးများသော Admissible Heuristics များမှာ

• Manhattan Distance: $|r_1 - r_2| + |c_1 - c_2|$ (၄ ဖက် ဓာတ်ဆန့်ကျင် ရွေ့လျားနိုင်ပြီး move တိုင်း cost = 1 ဖြစ်လျှင်)
• Chebyshev Distance: $\max(|r_1 - r_2|, |c_1 - c_2|)$ (၈ ဖက် ထောင့်ဖြတ်ပါ ရွေ့လျားနိုင်ပြီး move တိုင်း cost = 1 ဖြစ်လျှင်)
• Euclidean Distance: $\sqrt{(r_1 - r_2)^2 + (c_1 - c_2)^2}$ (ပကတိ ထောင့်ဖြတ် အကွာအဝေး cost = $\sqrt{2}$ ဖြစ်လျှင်)

Practical Problem: Shortest Path in Binary Matrix (A* Implementation)

m × n grid တစ်ခုတွင် 0 သည် သွားလာနိုင်သော လမ်းကြောင်းဖြစ်ပြီး 1 သည် အတားအဆီး ဖြစ်သည်။ ဘယ်အပေါ်ထောင့် (0,0) မှ ညာအောက်ထောင့် (m-1,n-1) သို့ ၄ ဖက် ရွေ့လျား၍ ရောက်ရှိနိုင်သော အတိုဆုံး အလှမ်း အရေအတွက် ကို A* Search သုံး၍ ရှာဖွေပါ။

Java Solution

import java.util.*;

public class AStarGrid {
    public int shortestPathAStar(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1;

        int targetR = m - 1, targetC = n - 1;

        // gScore[r][c]: Start မှ (r,c) သို့ တကယ် ရောက်ရှိခဲ့သော အလှမ်း အရေအတွက်
        int[][] gScore = new int[m][n];
        for (int[] row : gScore) Arrays.fill(row, Integer.MAX_VALUE);
        gScore[0][0] = 0;

        // Min-Heap: (fScore, r, c)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        // f = g + h -> 0 + Manhattan Distance
        int startH = Math.abs(0 - targetR) + Math.abs(0 - targetC);
        pq.offer(new int[]{startH, 0, 0});

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int r = cur[1], c = cur[2];

            if (r == targetR && c == targetC) return gScore[r][c];

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    int tentG = gScore[r][c] + 1;
                    if (tentG < gScore[nr][nc]) {
                        gScore[nr][nc] = tentG;
                        int h = Math.abs(nr - targetR) + Math.abs(nc - targetC);
                        pq.offer(new int[]{tentG + h, nr, nc});
                    }
                }
            }
        }
        return -1;
    }
}

Complexity Analysis:

• Time Complexity: Worst-case တွင် $O(V \log V)$ (Dijkstra နှင့် တူညီသည်) ဖြစ်သော်လည်း လက်တွေ့တွင် ကောင်းမွန်သော Heuristic ကြောင့် ရှာဖွေရသည့် Node အရေအတွက်ကို မြောက်များစွာ လျှော့ချပေးပါသည်။
• Space Complexity: $O(V)$ — Grid matrix တန်ဖိုးများ နှင့် Heap memory အတွက် ဖြစ်ပါသည်။

Bellman-Ford Algorithm — Negative Edge Weights

Dijkstra ၏ အားနည်းချက်နှင့် Bellman-Ford

Dijkstra's Algorithm သည် Greedy ချဉ်းကပ်မှုကို သုံးထားသဖြင့် Edge weight များတွင် အနုတ်ကိန်း (Negative weight) ပါဝင်လာပါက အဖြေမှားယွင်းသွားတတ်ပါတယ်။ အကြောင်းမှာ Dijkstra သည် Node တစ်ခုကို Finalize လုပ်ပြီးပါက ပြန်လည် စစ်ဆေးခြင်း မရှိတော့ပေ။ သို့သော် Negative weight ရှိနေပါက Finalize လုပ်ပြီးသား Node သို့ နောက်မှ ပိုမို သက်သာသော လမ်းကြောင်း ရောက်ရှိလာနိုင်သောကြောင့် ဖြစ်ပါတယ်။

ဒီလို Negative weight များ ပါဝင်သော Graph များအတွက် Dynamic Programming သဘောတရားကို အခြေခံထားသည့် Bellman-Ford Algorithm ကို သုံးရပါတယ်။

$V-1$ ကြိမ် Relaxation လုပ်ဆောင်ခြင်း

Vertex အရေအတွက် V ခု ရှိသော Graph တစ်ခုတွင် Cycle မပါဝင်သော အတိုဆုံး လမ်းကြောင်း တစ်ခု၌ အများဆုံး ပါဝင်နိုင်သည့် Edge အရေအတွက်သည် V - 1 ခု ဖြစ်ပါတယ်။

Bellman-Ford Algorithm သည် Graph အတွင်းရှိ Edge အားလုံးကို V - 1 ကြိမ်တိုင်တိုင် ထပ်ခါထပ်ခါ Relax လုပ်ဆောင်ပေးခြင်း ဖြင့် အတိုဆုံး လမ်းကြောင်းကို ရှာဖွေပေးပါတယ်။

   for i = 1 to V - 1:
       for each edge (u, v, weight):
           if dist[u] + weight < dist[v]:
               dist[v] = dist[u] + weight

Negative Cycle Detection

အကယ်၍ V - 1 ကြိမ်မကဘဲ V ကြိမ်မြောက် ထပ်မံ Relax လုပ်သည့်အခါတွင်ပင် တန်ဖိုးများ ထပ်မံ လျော့နည်းသွားသေးပါက ထို Graph ၌ Negative Cycle (လည်ပတ်လေ အကွာအဝေး လျော့နည်းလေဖြစ်သော Cycle) ရှိနေကြောင်း အတည်ပြုနိုင်ပါတယ်။ Negative Cycle ရှိနေပါက အတိုဆုံး လမ်းကြောင်း တန်ဖိုးသည် $-\infty$ သို့ ဦးတည်သွားမည် ဖြစ်၍ အဖြေရှာရန် မဖြစ်နိုင်တော့ပါ။

Dijkstra vs Bellman-Ford:

• Dijkstra: Edge weights ≥ 0 သာ လက်ခံသည်၊ မြန်ဆန်သည် $O(E \log V)$။
• Bellman-Ford: Negative edge weight များ ပါဝင်နိုင်သည်၊ Negative Cycle ကို စစ်ဆေးပေးနိုင်သည်၊ ပိုမိုနှေးကွေးသည် $O(V \times E)$။

Floyd-Warshall Algorithm — All-Pairs Shortest Path

အခြေခံ သဘောတရား

Dijkstra နှင့် Bellman-Ford တို့သည် Node တစ်ခုတည်းမှ ကျန် Node များသို့ အတိုဆုံး လမ်းကြောင်း (Single-Source) ကို ရှာဖွေပေးခြင်း ဖြစ်ပါတယ်။ သို့သော် Node တိုင်းမှ ကျန် Node တိုင်းသို့ (All-Pairs) အတိုဆုံး လမ်းကြောင်း ဇယားတစ်ခုလုံး သိရှိလိုပါက Floyd-Warshall Algorithm ကို သုံးရပါတယ်။

Floyd-Warshall ၏ အဓိက သဘောတရားမှာ Intermediate Node DP ဖြစ်ပါတယ်။
"Node i မှ j သို့ သွားရာတွင် ကြားခံ Node k ကို ဖြတ်သန်း ခွင့်ပြုလိုက်ပါက ပိုမို သက်သာသော လမ်းကြောင်း ရှိလာမည်လား" ဆိုသည်ကို ကြားခံ Node k တစ်ခုစီအတွက် တွက်ချက်သွားခြင်း ဖြစ်ပါတယ်။

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

Java Implementation

public class FloydWarshall {
    public void floydWarshall(int V, int[][] graph) {
        int[][] dist = new int[V][V];

        // ဇယားအား စတင် ပြင်ဆင်ခြင်း
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // Intermediate node k အား ကြားခံအဖြစ် ဖြတ်သန်းကြည့်ခြင်း
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(V^3)$ — 3-nested loops သုံးထားသောကြောင့် ဖြစ်ပြီး Vertex အရေအတွက် အနည်းငယ် (ဥပမာ V ≤ 400) ရှိသော Graph များအတွက် အလွန် သင့်တော်ပါသည်။
• Space Complexity: $O(V^2)$ — 2D distance matrix အတွက် ဖြစ်ပါသည်။

Union-Find (Disjoint-Set) Data Structure

အခြေခံ သဘောတရားနှင့် Operations

Union-Find (သို့မဟုတ် Disjoint-Set Union - DSU) ဆိုသည်မှာ အစိတ်အပိုင်း (elements) အများအပြားကို ထပ်တူမကျသော အုပ်စု (disjoint sets) မျာအဖြစ် ခွဲခြား သိုလှောင်ထားပြီး၊ အောက်ပါ အဓိက Operations နှစ်ခုကို အလွန် မြန်ဆန်စွာ လုပ်ဆောင်ပေးနိုင်သည့် Data Structure ဖြစ်ပါတယ် —

1. find(x): Element x ပါဝင်သော အုပ်စု၏ ပင်မ ကိုယ်စားလှယ် Root ကို ရှာဖွေပေးသည်။
2. union(x, y): Element x နှင့် y တို့ ပါဝင်သော အုပ်စု နှစ်ခုကို အုပ်စု တစ်ခုတည်းအဖြစ် ပေါင်းစည်း ပေးသည်။

   union(1,2), union(3,4), union(2,4) လုပ်ဆောင်ပြီးနောက် သစ်ပင် ပုံသဏ္ဌာန်:

         1                 ( Root 1 သည် အုပ်စုတစ်ခုလုံး၏ ကိုယ်စားလှယ် ဖြစ်သည် )
        / \
       2   3
           |
           4
   find(4) -> 4 -> 3 -> 1 (Root = 1)
   find(2) -> 2 -> 1      (Root = 1)  ⇒  2 နှင့် 4 သည် အုပ်စုတူညီကြသည် ✓

Optimizations: Path Compression နှင့် Union by Rank

ရိုးရိုး Union-Find သည် သစ်ပင် ပုံသဏ္ဌာန် အောက်သို့ ရှည်လျားသွားပါက $O(n)$ အထိ နှေးကွေးသွားနိုင်ပါတယ်။ ဒါကို ကာကွယ်ဖို့ အရေးကြီးသော Optimization နည်းလမ်း နှစ်ခုကို တွဲဖက် သုံးရပါတယ် —

• Path Compression (find တွင် သုံးသည်): Root ကို ရှာဖွေသည့် လမ်းကြောင်းပေါ်ရှိ Node အားလုံးကို Root သို့ တိုက်ရိုက် ချိတ်ဆက်ပေးလိုက်ခြင်းဖြင့် သစ်ပင်၏ အမြင့်ကို ပြားသွားစေပါသည်။
• Union by Rank (union တွင် သုံးသည်): အုပ်စု နှစ်ခု ပေါင်းစပ်သည့်အခါ အမြင့်နိမ့်သော (Rank နည်းသော) သစ်ပင်ကို အမြင့်မြင့်သော သစ်ပင်၏ အောက်သို့သာ သွားရောက် ချိတ်ဆက်စေပါသည်။

ဒီ Optimization နှစ်ခုကို သုံးလိုက်ပါက Operation တစ်ခု၏ အချိန်ကြာမြင့်ချိန်သည် $O(\alpha(n))$ (Inverse Ackermann function) သို့ ရောက်ရှိသွားပြီး လက်တွေ့တွင် $O(1)$ နီးပါး အလွန် မြန်ဆန်သွားပါတယ်။

Practical Problem: Redundant Connection (Cycle Detection)

Node n ခု ပါဝင်သော undirected tree တွင် edge တစ်ခု ပိုမို ထည့်သွင်းလိုက်သဖြင့် cycle ဖြစ်ပေါ်သွားသည်။ ပေးထားသော edge များထဲမှ ဖယ်ရှားလိုက်ပါက မူလ tree ပြန်လည် ဖြစ်ပေါ်စေမည့် redundant edge ကို Union-Find သုံး၍ ရှာဖွေပါ။

Java Solution

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // Path Compression
        }
        return parent[i];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false; // အုပ်စု တူညီပြီးသားဖြစ်၍ cycle ဖြစ်ပေါ်စေသည်

        // Union by Rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

class SolutionRedundant {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);

        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) {
                return edge; // Union မဖြစ်ဘဲ cycle ဖြစ်စေသော redundant edge အား ပြန်ပေးခြင်း
            }
        }
        return new int[0];
    }
}

Complexity Analysis:

• Time Complexity: $O(N \cdot \alpha(N)) \approx O(N)$ — Edge တစ်ခုစီကို Union-Find လုပ်ဆောင်ခြင်း ဖြစ်ပါတယ်။
• Space Complexity: $O(N)$ — Parent နှင့် Rank array များအတွက် ဖြစ်ပါတယ်။

Minimum Spanning Tree (MST)

Spanning Tree နှင့် Cut Property

Weighted undirected graph တစ်ခုတွင် Vertex အားလုံးကို ဆက်စပ်မှု ရှိစေရန် (connected ဖြစ်စေရန်) Edge များကို ရွေးချယ်ရာ၌ Edge weight စုစုပေါင်း အနည်းဆုံး ဖြစ်အောင် ရွေးချယ်ထားသော သစ်ပင် structure ကို Minimum Spanning Tree (MST) ဟု ခေါ်ပါတယ်။ Node n ခု ပါဝင်သော Graph တစ်ခု၏ MST တွင် Cycle မပါဝင်ဘဲ Edge အတိအကျ n - 1 ခု ပါဝင်ရပါမည်။

MST ကို ရှာဖွေရာတွင် Greedy logic မှန်ကန်ကြောင်း သက်သေပြသည့် အဓိက သီအိုရီမှာ Cut Property ဖြစ်ပါတယ် — "Graph အား အုပ်စု နှစ်ခု ခွဲခြားကြည့်ပါက ထိုအုပ်စု နှစ်ခုကြားကို ချိတ်ဆက်ပေးသော Edge များထဲမှ အကွာအဝေး အနည်းဆုံး (အသက်သာဆုံး) Edge သည် MST ၏ အစိတ်အပိုင်း ဖြစ်ရမည်"။

MST ရှာဖွေရန် နာမည်ကျော် Algorithm နှစ်ခု ရှိပါတယ် — Kruskal's Algorithm နှင့် Prim's Algorithm။

Kruskal's Algorithm vs Prim's Algorithm

1. Kruskal's Algorithm (Edge-centric):

   • Graph အတွင်းရှိ Edge အားလုံးကို Edge weight အလိုက် ငယ်စဉ်မှ ကြီးစဉ် စီစဉ်လိုက်ပါတယ်။
   • Weight အနည်းဆုံး Edge မှ စတင်၍ Cycle မဖြစ်ပေါ်ပါက (Union-Find ဖြင့် စစ်ဆေး၍) MST ထဲသို့ ထည့်သွင်းပါတယ်။ Edge အရေအတွက် n - 1 ခု ပြည့်ပါက ရပ်တန့်ပါတယ်။
   • Sparse Graph (Edge အရေအတွက် နည်းသော Graph) တွင် အသုံးပြုရန် ပိုမို သင့်တော်ပါသည်။

2. Prim's Algorithm (Node-centric):

   • Node တစ်ခုမှ စတင်၍ လက်ရှိ MST သစ်ပင်နှင့် ချိတ်ဆက်နိုင်သော Edge များထဲမှ အသက်သာဆုံး Edge ကို Min-Heap သုံး၍ ရွေးချယ် ပေါင်းစည်းသွားခြင်း ဖြစ်ပါတယ်။
   • Dense Graph (Edge အရေအတွက် များပြားသော Graph) တွင် အသုံးပြုရန် ပိုမို သင့်တော်ပါသည်။

Practical Problem: Min Cost to Connect All Points (Kruskal's MST)

2D plane ပေါ်ရှိ coordinates points ကို ပေးထားသည်။ Point နှစ်ခုကြား ချိတ်ဆက်မှု စရိတ်သည် Manhattan distance (|x1 - x2| + |x1 - x2|) ဖြစ်သည်။ Point အားလုံး ချိတ်ဆက်မိစေရန် ကုန်ကျမည့် အနည်းဆုံး စရိတ် ကို Kruskal's Algorithm ဖြင့် ရှာဖွေပါ။

Java Solution

import java.util.*;

class SolutionMST {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();

        // Point အားလုံးကြားရှိ Edge များနှင့် Manhattan Distance များကို တွက်ချက်ခြင်း
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{dist, i, j});
            }
        }

        // Edge များကို Weight အလိုက် ငယ်စဉ်မှ ကြီးစဉ် စီစဉ်ခြင်း
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));

        UnionFind uf = new UnionFind(n);
        int mstCost = 0;
        int edgesUsed = 0;

        for (int[] edge : edges) {
            int weight = edge[0];
            int u = edge[1];
            int v = edge[2];

            if (uf.union(u, v)) {
                mstCost += weight;
                edgesUsed++;
                if (edgesUsed == n - 1) break; // Edge n - 1 ခု ပြည့်ပါက MST ရရှိပြီ ဖြစ်သည်
            }
        }
        return mstCost;
    }
}

Complexity Analysis:

• Time Complexity: $O(N^2 \log(N^2)) = O(N^2 \log N)$ — Point အားလုံးကြား Edge စုစုပေါင်း $N^2$ ခုအား Sorting လုပ်ဆောင်ရသောကြောင့် ဖြစ်ပါတယ်။
• Space Complexity: $O(N^2)$ — Edge List သိမ်းဆည်းရန် ဖြစ်ပါတယ်။

Real-world Applications Summary

ယခုအခန်း၌ လေ့လာခဲ့သော Advanced Graph Algorithm များသည် သီအိုရီ သက်သက် မဟုတ်ဘဲ Software Engineering နယ်ပယ် အသီးသီးတွင် အဓိက အုတ်မြစ်အဖြစ် ပါဝင်နေပါတယ် —

1. Package Management & Build Systems (Topological Sort): npm, pip သို့မဟုတ် Gradle တို့တွင် Dependency အစဉ်လိုက် Install / Compile လုပ်ဆောင်နိုင်ရန် သုံးစွဲသည်။
2. GPS Routing & Navigation (Dijkstra & A Search):* Google Maps, Apple Maps သို့မဟုတ် Game AI Pathfinding တွင် အတိုဆုံး သွားလာနိုင်မည့် လမ်းကြောင်း ရှာဖွေရာ၌ သုံးစွဲသည်။
3. Network Routing Protocols (Dijkstra & Bellman-Ford): Internet Router များအကြား Packet ဒေတာများ အမြန်ဆုံးနှင့် အမှန်ကန်ဆုံး ကူးပြောင်းနိုင်ရန် သုံးစွဲသည်။
4. Infrastructure Grid Design (Minimum Spanning Tree): လျှပ်စစ်ဓါတ်အားလိုင်းများ၊ ရေပိုက်လိုင်းများနှင့် ကွန်ရက် Cable လိုင်းများကို စရိတ် အနည်းဆုံးဖြင့် လွှမ်းခြုံ ချိတ်ဆက်နိုင်ရန် သုံးစွဲသည်။
5. Social Network & Image Processing (Union-Find): Social media ပလက်ဖောင်းများတွင် သူငယ်ချင်း အုပ်စုများ ခွဲခြားခြင်းနှင့် Image Segmentation တွင် အရာဝတ္ထုများ အုပ်စုဖွဲ့ခြင်းတို့၌ သုံးစွဲသည်။