Dijkstra's Algorithm สำหรับ Adjacency List Representation

Dijkstra's Algorithm ด้วย Adjacency List (รายการความติดกัน) เหมาะสำหรับกราฟเบา (Sparse Graph) ใช้ Priority Queue (Min-Heap) ทำให้เร็วขึ้น

ความซับซ้อน (Complexity)

• Time: O(E log V) โดย E = จำนวนขอบ, V = จำนวนโหนด
• Space: O(V + E)

แนวคิดการทำงาน

1. สร้าง Adjacency List: โหนดแต่ละตัวเก็บรายการ (เพื่อนบ้าน, น้ำหนัก)
2. ใช้ Priority Queue (Min-Heap) เก็บ (ระยะทาง, โหนด)
3. Extract-Min: ดึงโหนดที่มีระยะทางน้อยที่สุด
4. Relaxation: อัปเดตระยะทางเพื่อนบ้าน

ตัวอย่างกราฟ (Adjacency List)

0: (1,3) (2,6)
1: (0,3) (2,2) (3,1)
2: (1,2) (3,1) (4,4) (5,2)
3: (1,1) (2,1) (4,2) (6,4)
4: (2,4) (3,2) (5,2) (6,1)
5: (2,2) (4,2) (6,1)
6: (3,4) (4,1) (5,1)

ผลลัพธ์ (จากโหนด 0)

0 to 1: Cost 3, Prev 0
0 to 2: Cost 5, Prev 1
0 to 3: Cost 4, Prev 1
0 to 4: Cost 6, Prev 3
0 to 5: Cost 7, Prev 2
0 to 6: Cost 7, Prev 4

อัลกอริทึม (Pseudocode)

dijkstra(graph, start)
  dist[V] = INF; prev[V] = -1
  dist[start] = 0

  PQ = MinHeap of (dist, vertex)
  PQ.push(0, start)

  while PQ not empty:
    (d, u) = PQ.pop()
    if d > dist[u]: continue  // stale entry

    for (v, weight) in graph.adj[u]:
      if dist[u] + weight < dist[v]:
        dist[v] = dist[u] + weight
        prev[v] = u
        PQ.push(dist[v], v)

ตัวอย่างโค้ด C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge { int dest, weight; };

void dijkstra(vector<vector<Edge>> &adj, int start) {
    int V = adj.size();
    vector<int> dist(V, INT_MAX), prev(V, -1);
    dist[start] = 0;

    // Min-heap: (distance, vertex)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto &e : adj[u]) {
            int v = e.dest, w = e.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < V; i++)
        if (i != start)
            cout << start << " to " << i << ": Cost " << dist[i] << ", Prev " << prev[i] << endl;
}

int main() {
    int V = 7;
    vector<vector<Edge>> adj(V);
    auto addEdge = [&](int u, int v, int w) { adj[u].push_back({v, w}); };

    addEdge(0,1,3); addEdge(0,2,6);
    addEdge(1,0,3); addEdge(1,2,2); addEdge(1,3,1);
    addEdge(2,1,2); addEdge(2,3,1); addEdge(2,4,4); addEdge(2,5,2);
    addEdge(3,1,1); addEdge(3,2,1); addEdge(3,4,2); addEdge(3,6,4);
    addEdge(4,2,4); addEdge(4,3,2); addEdge(4,5,2); addEdge(4,6,1);
    addEdge(5,2,2); addEdge(5,4,2); addEdge(5,6,1);
    addEdge(6,3,4); addEdge(6,4,1); addEdge(6,5,1);

    dijkstra(adj, 0);
}

เปรียบเทียบ Adjacency Matrix vs List