Single-Source Shortest Paths, Nonnegative Weights (Dijkstra Algorithm)

Single-Source Shortest Path (Non-negative Weights) หรือ Dijkstra Algorithm หาระยะทางสั้นที่สุดจาก Source Vertex ไปโหนดอื่นๆ ในกราฟ G(V,E) ที่มี Adjacency Matrix และน้ำหนักไม่ติดลบ

จากโหนดเริ่มต้น หาระยะทางน้อยที่สุดไปโหนดอื่นๆ กราฟแสดงด้วย Adjacency Matrix (Cost Matrix)

Input

Adjacency Matrix

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

Output

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

Algorithm

dijkstraShortestPath(n, dist, next, start)

Input: จำนวนโหนด n, Distance list, Next list, Start vertex
Output: เส้นทางสั้นที่สุดจาก Start ไปทุกโหนด

Begin
    create status list for current status of selected node
    for all vertices u in V do
        status[u] := unconsidered
        dist[u] := distance from source using cost matrix
        next[u] := start
    done
    status[start] := considered, dist[start] := 0, next[start] := φ
    while take unconsidered vertex u with minimum distance do
        status[u] := considered
        for all vertex v in V do
            if status[v] = unconsidered then
                if dist[v] > dist[u] + cost[u,v] then
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
                done
            done
        done
End

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

#include <iostream>
#define V 7
#define INF 999
using namespace std;

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 minimum(int *status, int *dis, int n) {
    int i, min = INF, index;
    for(i = 0; i < n; i++)
        if(dis[i] < min && status[i] == 1) {
            min = dis[i]; index = i;
        }
    if(status[index] == 1) return index;
    else return -1;
}

void dijkstra(int n, int *dist, int *next, int s) {
    int status[V], u, v;
    for(u = 0; u < n; u++) {
        status[u] = 1; // unconsidered
        dist[u] = costMat[u][s];
        next[u] = s;
    }
    status[s] = 2; dist[s] = 0; next[s] = -1;
    while((u = minimum(status, dist, n)) > -1) {
        status[u] = 2;
        for(v = 0; v < n; v++)
            if(status[v] == 1)
                if(dist[v] > dist[u] + costMat[u][v]) {
                    dist[v] = dist[u] + costMat[u][v];
                    next[v] = u;
                }
    }
}

main() {
    int dis[V], next[V], i, start = 0;
    dijkstra(V, dis, next, start);
    for(i = 0; i < V; i++)
        if(i != start)
            cout << start << " to " << i << ", Using: " << next[i] << ", Cost: " << dis[i] << endl;
}

Output

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