โปรแกรม C++ ใช้ Dijkstra's Algorithm ด้วย Set

บทนำ

นี่คือโปรแกรม C++ ใช้ Dijkstra's Algorithm ด้วย Set เราต้องมีสองเซต สร้าง shortest path tree จาก source node เป็นราก เซตหนึ่งเก็บโหนดที่อยู่ใน shortest path tree อีกเซตเก็บโหนดที่ยังไม่ได้รวม ทุกขั้นตอน หาโหนดที่อยู่ในเซตที่ยังไม่รวมและมีระยะทางน้อยที่สุดจาก source

อัลกอริทึม

Begin
  function dijkstra() หาระยะทางต่ำสุด:
    1) สร้างเซต Set เก็บโหนดที่อยู่ใน shortest path tree เริ่มต้นว่าง
    2) กำหนดค่าระยะทางให้ทุกโหนดเป็น INFINITE ยกเว้น source = 0
    3) While Set ไม่ครบทุกโหนด
       a) เลือกโหนด u ที่ไม่อยู่ใน Set และมีระยะทางน้อยที่สุด
       b) ใส่ u เข้า Set
       c) อัปเดตระยะทางของโหนดติดกับ u: ถ้า dist[u] + weight(u,v) < dist[v] ให้อัปเดต dist[v]
End

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

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

#define N 5

int minDist(int dist[], bool Set[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < N; v++)
        if (Set[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

int printSol(int dist[], int n) {
    cout << "Vertex Distance from Source\n";
    for (int i = 0; i < N; i++)
        cout << " \t\t \n" << i << " \t\t " << dist[i];
}

void dijkstra(int g[N][N], int src) {
    int dist[N];
    bool Set[N];
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX, Set[i] = false;
    dist[src] = 0;
    for (int c = 0; c < N - 1; c++) {
        int u = minDist(dist, Set);
        Set[u] = true;
        for (int v = 0; v < N; v++)
            if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
    printSol(dist, N);
}

int main() {
    int g[N][N] = {
        {0, 4, 0, 0, 0},
        {4, 0, 7, 0, 0},
        {0, 8, 0, 9, 0},
        {0, 0, 7, 0, 6},
        {0, 2, 0, 9, 0}
    };
    dijkstra(g, 0);
    return 0;
}

ผลลัพธ์

Vertex Distance from Source
0 0
1 4
2 11
3 20
4 26