Thuật toán Dijkstra tìm đường đi ngắn nhất (Ma trận kề)

Bài toán: từ đỉnh xuất phát đến mọi đỉnh khác, tìm khoảng cách nhỏ nhất. Đồ thị biểu diễn bằng ma trận kề (cost matrix).

Độ phức tạp với ma trận kề: O(V²) với V là số đỉnh.

Input và Output

Input: Ma trận chi phí: (hình ảnh)
Output:
0 đến 1, Qua: 0, Chi phí: 3
0 đến 2, Qua: 1, Chi phí: 5
0 đến 3, Qua: 1, Chi phí: 4
0 đến 4, Qua: 3, Chi phí: 6
0 đến 5, Qua: 2, Chi phí: 7
0 đến 6, Qua: 4, Chi phí: 7

Thuật toán

dijkstraShortestPath(n, dist, next, start)
Input: Số đỉnh n, mảng dist, mảng next, đỉnh bắt đầu
Output: Đường đi ngắn nhất từ start đến mọi đỉnh

Begin
  tạo mảng status lưu trạng thái đỉnh
  for mọi đỉnh u trong V do
    status[u] := unconsidered
    dist[u] := khoảng cách từ source dùng cost matrix
    next[u] := start
  done
  status[start] := considered, dist[start] := 0, next[start] := ∅
  while lấy đỉnh u chưa considered có dist nhỏ nhất do
    status[u] := considered
    for mọi đỉnh v trong 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
  done
End

Ví dụ (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 min = INF, index = -1;
    for(int i = 0; i < n; i++)
        if(dis[i] < min && status[i] == 1) { min = dis[i]; index = i; }
    return (status[index] == 1) ? index : -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; 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 && dist[v] > dist[u] + costMat[u][v]) {
                dist[v] = dist[u] + costMat[u][v];
                next[v] = u;
            }
    }
}

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

Kết quả

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

Lưu ý: Phiên bản ma trận kề phù hợp đồ thị dày đặc (dense graph). Với đồ thị thưa (sparse), dùng danh sách kề + priority queue cho O(E log V).