Dijkstra's Algorithm: the Shortest Path in a Weighted Graph

Lesson 11 of 17 · Graphs and trees

BFS finds the shortest path when all the edges have the same length. When the edges have different lengths (kilometres, minutes, prices), Dijkstra's algorithm is used. It works for graphs whose weights are not negative, and with a priority_queue it processes even a million edges in a fraction of a second.

Before you start: prerequisites – BFS, priority_queue.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea

        4
   1 ------- 2
   |  \      |
 1 |   \ 7   | 2
   |    \    |
   3 ------- 4 ---- 5
        5       3

The edges: 1–2 (4), 1–3 (1), 1–4 (7), 2–4 (2), 3–4 (5), 4–5 (3).

We keep the array dist[v] – the shortest distance found so far from the start to v (∞ at the beginning, and 0 for the start). In every step we take the unprocessed vertex with the smallest dist: its distance is surely final, because any other path would go through a vertex that is already farther away. Then we try to shorten the path to its neighbours (relaxation): if dist[v] + w < dist[u], then dist[u] = dist[v] + w.

Dijkstra from vertex 1
StepWe take the vertexdist[1..5] after the step
start0 ∞ ∞ ∞ ∞
11 (dist 0)0 4 1 7 ∞
23 (dist 1)0 4 1 6 ∞ (1→3→4 = 6 < 7)
32 (dist 4)0 4 1 6 ∞ (1→2→4 = 6, not shorter)
44 (dist 6)0 4 1 6 9
55 (dist 9)0 4 1 6 9

A program with priority_queue

We get the smallest dist quickly from a priority queue that holds the pairs (distance, vertex), with the smallest at the top. The same vertex can be in the queue several times (every time its distance is shortened); we skip outdated entries with the check d > dist[v].

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const long long INF = 1e18;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);   // graph[u] = {(neighbour, weight)}
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});                // an undirected graph
    }
    int s = 1;
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue;                 // an outdated entry – v has already been processed via a shorter path
        for (auto [u, w] : graph[v]) {
            if (dist[v] + w < dist[u]) {           // relaxation
                dist[u] = dist[v] + w;
                pq.push({dist[u], u});
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) cout << v << ": unreachable" << endl;
        else cout << v << ": " << dist[v] << endl;
    }
    return 0;
}

Example (the graph from the drawing)

Input

5 6
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 3

Output

1: 0
2: 4
3: 1
4: 6
5: 9

The notation auto [d, v] = pq.top(); splits the pair into two variables (C++17). With older compilers you write long long d = pq.top().first; int v = pq.top().second;.

Reconstructing the path

To print the path itself too, at every relaxation we remember where we came from: prev[u] = v. The path to the target t is obtained by following prev backwards from t to the start and reversing it – see task 1.

Complexity and limitations

Value
ComplexityO((n + m) log n)
Negative weightsdoes not work – use Bellman-Ford
All the weights are equalBFS is enough, O(n + m)
A directed graphworks the same – add the edge only in one direction
The graph is a DAGfaster: DP in topological order, works with negative weights too

Why it does not work with negative edges: when we take the vertex with the smallest dist, we assume that it cannot be reached by a shorter path later. A negative edge would make exactly that possible.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

The shortest path from 1 to n

An undirected weighted graph is given. Print the length of the shortest path from vertex 1 to vertex n and the path itself, or -1 if there is no path.

Example 1

Input

5 6
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 3

Output

9
1 3 4 5

Example 2

Input

3 1
1 2 5

Output

-1
TASK 02Difficulty: harder

The nearest hospital

In a city with n crossroads and m two-way streets (with lengths) there are k hospitals. For every crossroads print the distance to the nearest hospital.

Input: n m k, then the k crossroads with a hospital, and then m streets u v w.

Example

Input

5 6 2
3 5
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 3

Output

1 5 0 3 0
Common mistakes and tips
  • Keep the distances in a long long – the sum of many weights easily exceeds 2·109.
  • priority_queue is a max-heap by default; for Dijkstra you need greater<…> (or store negative distances).
  • Without the check if (d > dist[v]) continue; the program is correct, but it can be much slower.
  • Dijkstra does not work with negative edge weights.

Check your knowledge

Open the quiz

Dijkstra's algorithm

1. For which graphs does Dijkstra's algorithm give a correct result?




2. Which vertex does Dijkstra process in the next step?




3. What is the relaxation of the edge v → u with the weight w?




4. What is the complexity of Dijkstra with a priority_queue?