Thuật toán Dijkstra với biểu diễn danh sách kề

Cho đồ thị G(V, E) biểu diễn bằng danh sách kề và đỉnh nguồn. Dijkstra tìm đường đi ngắn nhất từ nguồn đến mọi đỉnh khác.

Dùng hai tập hợp: S (đã xét) và Q (chưa xét). Mỗi phase lấy đỉnh chưa xét có khoảng cách nhỏ nhất từ nguồn. Dùng mảng prev lưu đỉnh trước để truy vết đường đi.

Độ phức tạp: O(E log V) với danh sách kề.

Input và Output

Input: Danh sách kề với chi phí cạnh (hình ảnh)
Output:
0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

Thuật toán

dijkstraShortestPath(g, dist, prev, start)
Input: Đồ thị g, mảng dist, mảng prev, đỉnh start
Output: Đường đi ngắn nhất từ start

Begin
  for u trong V - {start} do dist[u] := ∞, prev[u] := ∅ done
  dist[start] = 0, prev[start] := ∅
  for u trong V do insert u vào queue Q done
  while Q không rỗng do
    u := phần tử min từ Q; xóa u khỏi Q; thêm u vào S
    for v kề với u do
      if dist[u] + cost(v) < dist[v] then
        dist[v] := dist[u] + cost(v)
        prev[v] := u
      done
    done
  done
End

Ví dụ (C++)

#include <iostream>
#include <set>
#include <list>
#include <algorithm>
using namespace std;

struct node { int dest; int cost; };

class Graph {
    int n; list<node> *adjList;
    void showList(int src, list<node> lt) { /* ... */ }
public:
    Graph(int n=0) : n(n) { if(n) adjList = new list<node>[n]; }
    void addEdge(int src, int dest, int cost) {
        adjList[src].push_back({dest, cost});
    }
    void displayEdges() { /* ... */ }
    friend void dijkstra(Graph g, int *dist, int *prev, int start);
};

void dijkstra(Graph g, int *dist, int *prev, int start) {
    int n = g.n;
    for(int u = 0; u < n; u++) { dist[u] = 9999; prev[u] = -1; }
    dist[start] = 0;
    set<int> S; list<int> Q;
    for(int u = 0; u < n; u++) Q.push_back(u);
    while(!Q.empty()) {
        auto it = min_element(Q.begin(), Q.end(), [&](int a, int b){ return dist[a] < dist[b]; });
        int u = *it; Q.remove(u); S.insert(u);
        for(auto &edge : g.adjList[u]) {
            if(dist[u] + edge.cost < dist[edge.dest]) {
                dist[edge.dest] = dist[u] + edge.cost;
                prev[edge.dest] = u;
            }
        }
    }
}

int main() {
    Graph g(7);
    // Thêm các cạnh (cả 2 chiều)
    g.addEdge(0,1,3); g.addEdge(0,2,6);
    g.addEdge(1,0,3); g.addEdge(1,2,2); g.addEdge(1,3,1);
    g.addEdge(2,0,6); g.addEdge(2,1,2); g.addEdge(2,3,1); g.addEdge(2,4,4); g.addEdge(2,5,2);
    g.addEdge(3,1,1); g.addEdge(3,2,1); g.addEdge(3,4,2); g.addEdge(3,6,4);
    g.addEdge(4,2,4); g.addEdge(4,3,2); g.addEdge(4,5,2); g.addEdge(4,6,1);
    g.addEdge(5,2,2); g.addEdge(5,4,2); g.addEdge(5,6,1);
    g.addEdge(6,3,4); g.addEdge(6,4,1); g.addEdge(6,5,1);
    int dist[7], prev[7];
    dijkstra(g, dist, prev, 0);
    for(int i = 1; i < 7; i++)
        cout << "0 to " << i << ", Cost: " << dist[i] << " Previous: " << prev[i] << endl;
}

Kết quả

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

Cải tiến: Dùng priority_queue (min-heap) thay cho list + min_element để đạt O(E log V) thực sự. Code trên dùng list để minh họa thuật toán cơ bản.