Dijkstra's Shortest Path Algorithm (อัลกอริทึมเดจก์สตรา) - Adjacency Matrix

Dijkstra's Algorithm หาเส้นทางสั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟที่มีน้ำหนักขอบ (Weighted Graph) เป็นบวกทั้งหมด ใช้ Adjacency Matrix (เมทริกซ์ความติดกัน) แสดงกราฟ

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

• Time: O(V²) โดย V = จำนวนโหนด (สำหรับ Adjacency Matrix)
• Space: O(V)

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

1. เริ่มต้น: ระยะทางจากต้นทางไปทุกโหนด = ∞, ต้นทาง = 0
2. เลือกโหนดที่ยังไม่ประมวลผล และมีระยะทางน้อยที่สุด
3. อัปเดตระยะทางของเพื่อนบ้าน: if dist[v] > dist[u] + weight(u,v)
4. ทำซ้ำจนประมวลผลทุกโหนด

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

    0  1  2  3  4  5  6
  0 0  3  6  ∞  ∞  ∞  ∞
  1 3  0  2  1  ∞  ∞  ∞
  2 6  2  0  1  4  2  ∞
  3 ∞  1  1  0  2  ∞  4
  4 ∞  ∞  4  2  0  2  1
  5 ∞  ∞  2  ∞  2  0  1
  6 ∞  ∞  ∞  4  1  1  0

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

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

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

dijkstra(n, costMatrix, start)
  dist[0..n-1] = INF
  visited[0..n-1] = false
  prev[0..n-1] = -1
  dist[start] = 0

  repeat n times:
    u = unvisited vertex with min dist
    if u == -1: break
    visited[u] = true

    for v = 0 to n-1:
      if not visited[v] AND costMatrix[u][v] != INF:
        if dist[v] > dist[u] + costMatrix[u][v]:
          dist[v] = dist[u] + costMatrix[u][v]
          prev[v] = u

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

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

#define V 7
#define INF 999

int costMat[V][V] = {
  {0, 3, 6, INF, INF, INF, INF},
  {3, 0, 2, 1, INF, INF, INF},
  {6, 2, 0, 1, 4, 2, INF},
  {INF, 1, 1, 0, 2, INF, 4},
  {INF, INF, 4, 2, 0, 2, 1},
  {INF, INF, 2, INF, 2, 0, 1},
  {INF, INF, INF, 4, 1, 1, 0}
};

int minDistance(int dist[], bool visited[]) {
    int min = INF, idx = -1;
    for (int i = 0; i < V; i++)
        if (!visited[i] && dist[i] < min) { min = dist[i]; idx = i; }
    return idx;
}

void dijkstra(int start) {
    int dist[V]; bool visited[V] = {false}; int prev[V];
    for (int i = 0; i < V; i++) { dist[i] = INF; prev[i] = -1; }
    dist[start] = 0;

    for (int count = 0; count < V-1; count++) {
        int u = minDistance(dist, visited);
        if (u == -1) break;
        visited[u] = true;

        for (int v = 0; v < V; v++)
            if (!visited[v] && costMat[u][v] != INF && dist[u] + costMat[u][v] < dist[v]) {
                dist[v] = dist[u] + costMat[u][v];
                prev[v] = u;
            }
    }

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

int main() { dijkstra(0); }

ข้อจำกัด

• ไม่ทำงานกับ Negative Weight Edges (ใช้ Bellman-Ford แทน)
• Adjacency Matrix ใช้พื้นที่ O(V²) เหมาะกราฟหนา (Dense)