โปรแกรม C++ สำหรับอัลกอริทึม Dijkstra หาเส้นทางสั้นที่สุด

อัลกอริทึม Dijkstra (หรือ Dijkstra's Shortest Path First algorithm, SPF algorithm) เป็นอัลกอริทึมสำหรับหาเส้นทางสั้นที่สุดระหว่างโหนดในกราฟ ซึ่งอาจแสดงถึงเครือข่ายถนน ตัวอย่างเช่น อัลกอริทึมสร้างต้นไม้ของเส้นทางสั้นที่สุดจากโหนดเริ่มต้น (source) ไปยังจุดอื่นๆ ทั้งหมดในกราฟ

Dijkstra's algorithm หาต้นไม้เส้นทางสั้นที่สุดจากโหนดแหล่งที่มา (single source node) โดยการสร้างชุดของโหนดที่มีระยะทางน้อยที่สุดจากแหล่งที่มา

กราฟมีสิ่งต่อไปนี้−

• โหนด (vertices/nodes) แทนด้วย v หรือ u ในอัลกอริทึม

• เส้นเชื่อมที่มีน้ำหนัก (weighted edges) เชื่อมสองโหนด: (u,v) แทนเส้นเชื่อม และ w(u,v) แทนน้ำหนักของมัน ในแผนภาพทางขวา น้ำหนักของแต่ละเส้นเขียนด้วยสีเทา

ขั้นตอนของอัลกอริทึม

• ตั้งค่าระยะทางของทุกโหนด = infinity ยกเว้นโหนดแหล่งที่มา ตั้งค่าระยะทางแหล่งที่มา = 0
• นำโหนดแหล่งที่มาเข้า min-priority queue ในรูปแบบ (distance, vertex) เนื่องจากการเปรียบเทียบใน min-priority queue จะอิงตามระยะทางของโหนด
• นำโหนดที่มีระยะทางน้อยที่สุดออกจาก priority queue (ในตอนแรกโหนดที่ถูกนำออก = source)
• อัปเดตระยะทางของโหนดที่เชื่อมกับโหนดที่ถูกนำออก กรณี "current vertex distance + edge weight < next vertex distance" แล้วนำโหนดพร้อมระยะทางใหม่เข้า priority queue
• ถ้าโหนดที่ถูกนำออกเคยเยี่ยมชมแล้ว ให้ข้ามไปโดยไม่ใช้
• ทำซ้ำอัลกอริทึมเดียวกันจนกว่า priority queue จะว่างเปล่า

กำหนดกราฟและโหนดแหล่งที่มาในกราฟ หาเส้นทางสั้นที่สุดจากแหล่งที่มาไปยังทุกโหนดในกราฟที่กำหนด กำหนดเมทริกซ์ G[][] ของน้ำหนักกราฟ, n จำนวนโหนดในกราฟ, u โหนดเริ่มต้น

อินพุต

G[max][max] = {{0,1,0,3,10},
               {1,0,5,0,0},
               {0,5,0,2,1},
               {3,0,2,0,6},
               {10,0,1,6,0}}
n=5 u=0

เอาต์พุต

Distance of node1=1 Path=1<-0
Distance of node2=5 Path=2<-3<-0
Distance of node3=3 Path=3<-0
Distance of node4=6 Path=4<-2<-3<-0

คำอธิบาย

• สร้างเมทริกซ์ต้นทุน C[][] จากเมทริกซ์ตyacency adj[][]. C[i][j] คือ ต้นทุนในการไปจากโหนด i ไปโหนด j หากไม่มีเส้นเชื่อมระหว่างโหนด i และ j แล้ว C[i][j] คือ infinity

• อาร์เรย์ visited[] เริ่มต้นเป็นศูนย์

for(i=0; i<n; i++) visited[i]=0;

• ถ้าโหนด 0 เป็นโหนดแหล่งที่มา visited[0] ถูกทำเครื่องหมายเป็น 1

• สร้างเมทริกซ์ระยะทาง โดยเก็บต้นทุนของโหนดจากโหนด 0 ถึง n-1 จากโหนดแหล่งที่มา 0

for(i=1; i<n; i++) distance[i] = cost[0][i];

เริ่มต้น ระยะทางของโหนดแหล่งที่มาถูกตั้งเป็น 0 คือ distance[0]=0;

for(i=1; i<n; i++) visited[i]=0;

• เลือกโหนด w ที่ distance[w] น้อยที่สุด และ visited[w] เป็น 0 ทำเครื่องหมาย visited[w] เป็น 1

• คำนวณระยะทางสั้นที่สุดของโหนดที่เหลือจากแหล่งที่มาใหม่

• พิจารณาเฉพาะโหนดที่ไม่ได้ทำเครื่องหมาย 1 ในอาร์เรย์ visited[] สำหรับการคำนวณระยะทางใหม่ คือ สำหรับแต่ละโหนด v

if(visited[v]==0) distance[v] = min(distance[v], distance[w] + cost[w][v])

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

#include<iostream>
#include<stdio.h>
using namespace std;

#define INFINITY 9999
#define max 5

void dijkstra(int G[max][max], int n, int startnode);

int main() {
    int G[max][max] = {{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
    int n = 5;
    int u = 0;
    dijkstra(G, n, u);
    return 0;
}

void dijkstra(int G[max][max], int n, int startnode) {
    int cost[max][max], distance[max], pred[max];
    int visited[max], count, mindistance, nextnode, i, j;
    
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            if(G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];
    
    for(i = 0; i < n; i++) {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;
    
    while(count < n - 1) {
        mindistance = INFINITY;
        for(i = 0; i < n; i++)
            if(distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }
        visited[nextnode] = 1;
        for(i = 0; i < n; i++)
            if(!visited[i])
                if(mindistance + cost[nextnode][i] < distance[i]) {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }
    
    for(i = 0; i < n; i++)
        if(i != startnode) {
            cout << "\nDistance of node" << i << "=" << distance[i];
            cout << "\nPath=" << i;
            j = i;
            do {
                j = pred[j];
                cout << "<-" << j;
            } while(j != startnode);
        }
}