Dijkstra

2017-07-21
Bài gốc

Codeforces 20C

Đề bài

Cho đồ thị vô hướng n đỉnh và m cạnh, mỗi cạnh có trọng số không âm w. Tìm đường đi ngắn nhất từ đỉnh 1 đến n.

Đồ thị có thể có vòng lặp, và có nhiều cạnh nối một cặp đỉnh.

Giới hạn:

  • 2 ≤ n ≤ 105; 0 ≤ m ≤ 105
  • 1 ≤ wi ≤ 106
Định dạng test

Input:

  • Dòng đầu là n và m.
  • m dòng tiếp theo; mỗi dòng 3 số u, v, w: cạnh nối đỉnh u và v có trọng số w

Các đỉnh được đánh số từ 1 đến n.

Output:

  • Nếu không tìm được đường đi ngắn nhất, in -1
  • Nếu có, in hai dòng:
    • Dòng đầu là chi phí nhỏ nhất.
    • Dòng thứ hai là đường đi ngắn nhất.

Ví dụ:

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
---
5
1 4 3 5
Thuật toán

Dijkstra

Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

typedef long long ll;
typedef pair<ll, int> lli;
const int N = 1e5 + 5;
const ll oo = 1e9;
int n, m, trace[N];
vector<lli> a[N];
vector<ll> dist;
priority_queue<lli, vector<lli>, greater<lli>> Q;

void print_path(int u) {
    if (u == 0) return;
    print_path(trace[u]);
    cout << u << ' ';
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // read input
    cin >> n >> m;
    REP(i,m) {
        int u, v; ll w;
        cin >> u >> v >> w;
        a[u].pb(mp(w, v));
        a[v].pb(mp(w, u));
    }

    // init for dijkstra
    dist.assign(n+1, oo);
    dist[1] = 0;
    Q.push(mp(0, 1));

    // dijkstra
    while(!Q.empty()) {
        lli p = Q.top(); Q.pop();
        int u = p.se;
        ll d = p.fi;
        if (d > dist[u]) continue;
        for(lli _ : a[u]) {
            int v = _.se;
            if (dist[u] + _.fi < dist[v]) {
                trace[v] = u;
                dist[v] = dist[u] + _.fi;
                Q.push(mp(dist[v], v));
            }
        }
    }

    // output
    if (dist[n] == oo)
        cout << -1;
    else {
        cout << dist[n] << '\n';
        print_path(n);
    }

    return 0;
}
Tính chất và ứng dụng

Sau khi chạy xong thuật toán Dijkstra, dist[u] chính là chi phí nhỏ nhất để đi từ đỉnh ban đầu là 1 đến u.

Một bài toán phổ biến: kiểm tra xem một đỉnh hoặc một cạnh của đồ thị có nằm trên đường đi ngắn nhất từ s đến t hay không? Đầu tiên sử dụng Dijkstra để xây dựng ds[u] là khoảng cách ngắn nhất từ s đến u, và dt[u] là khoảng cách ngắn nhất từ u đến t:

  • Xét đỉnh u, nếu có ds[u] + dt[u] = ds[t] (= dt[s]) thì u thuộc đường đi ngắn nhất từ s đến t.
  • Xét cạnh (u, v), có 2 khả năng cho con đường ngắn nhất từ s đến t và đi qua (u, v):
    • s -> u -> v -> t, tổng chi phí: ds[u] + w(u, v) + dt[v].
    • t -> u -> v -> s, tổng chi phí: st[u] + w(u, v) + ds[v].
    • Nếu một trong hai chi phí trên bằng ds[t] (hoặc dt[s]) thì cạnh (u, v) thuộc đường đi ngắn nhất từ s đến t.

Một bài toán khác: tính f[u] là số con đường có chi phí ngắn nhất khi đi từ s đến u, có thể định dạng đoạn code trên một chút như sau:

  • Khởi tạo:
1
2
3
4

// init for dijkstra
...
f.assign(n+1, 0);
f[1] = 1;
  • Truy hồi:
1
2
3
4
5
6
7
8
9
10

// dijkstra
while(!Q.empty()) {
  ...
  if (dist[u] + _.fi < dist[v]) {
      ...
      f[v] = f[u];
  }
  else if (dist[u] + _.fi == dist[v])
      f[v] += f[u];
}
Độ phức tạp

O(ElogE), với |E| là số cạnh của đồ thị.