A table between stations
You are given a directed graph: vertices, arcs and their weights. Weights can be negative, but the graph has no cycles of negative weight. Some vertices are stations. For each ordered pair of stations, find the weight of the shortest path from the first to the second.
One of the tests is a piece of the streets of Almaty around Republic Square with the weights from the article: the energy of an electric car, negative for descents.
Input
The first line holds the number of vertices n, arcs m and stations k (1 ≤ n ≤ 600, 0 ≤ m ≤ 3000, 1 ≤ k ≤ 50). Then come m lines u v w: an arc from u to v of weight w, |w| ≤ 106; loops and multiple arcs are possible. The last line holds k distinct station numbers.
Output
k lines of k numbers: at position (i, j) the weight of the shortest path from the i-th station to the j-th, or “*” if there is no path. The diagonal holds 0.
Examples
Example 1
4 5 3 1 2 1 1 3 3 3 2 -5 2 4 1 3 4 6 1 2 4
0 -2 -1 * 0 1 * * 0
Example 2
5 4 4 1 2 3 2 3 -2 3 1 4 4 5 -7 1 3 4 5
0 1 * * 4 0 * * * * 0 -7 * * * 0
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Bellman–Ford from each station is k·n·m, up to 9·107 relaxations; Floyd–Warshall is n3 = 2·108. Both are tight in Python. Dijkstra from each station would be fast, but the weights are negative, and the very first example breaks it. Can the weights be made non-negative?
2Hint 2
Add a vertex with an arc of weight 0 to every vertex, and compute distances from it with Bellman–Ford. What can be said about w(u, v) + δ(u) − δ(v)?
3The idea
Johnson’s algorithm. The distances δ from the added vertex satisfy δ(v) ≤ δ(u) + w(u, v), so the reduced weights w + δ(u) − δ(v) are non-negative. The weight of any path from s to t changes by δ(s) − δ(t), the same number for all paths, so the shortest paths are the same. Dijkstra from each station on the reduced weights and the reverse conversion: the distance minus δ(s) plus δ(t). The added vertex need not be built: it is enough to start Bellman–Ford with all δ equal to zero.
4Walkthrough
In the first example a direct arc of weight 1 leads from vertex 1 to vertex 2, but the path 1 → 3 → 2 costs 3 − 5 = −2. Dijkstra without reweighting takes vertex 2 out with weight 1 before vertex 3 and never touches it again. Bellman–Ford with all δ zero finds δ = (0, −5, 0, −4) in one round and changes nothing in the second. The reduced weights: 1 → 2 is 1 + 0 − (−5) = 6, 1 → 3 is 3, 3 → 2 is −5 + 0 − (−5) = 0, 2 → 4 is 1 − 5 + 4 = 0, 3 → 4 is 6 + 0 + 4 = 10; none negative. Dijkstra from vertex 1 finds a path to vertex 2 through vertex 3 of weight 3, and the reverse conversion gives 3 − 0 + (−5) = −2. To vertex 4, 3 − 0 + (−4) = −1.
4+Solution
5Complexity
Bellman–Ford is O(n·m), up to 1.8·106 relaxations, and in the sixth test, where a chain is listed from the end, it really needs almost all n rounds. Then k runs of Dijkstra of O(m log n) each. A few million operations in all.
6Common mistakes
- Dijkstra on the original weights. The first example.
- Forgetting the reverse conversion. The distance in reduced weights is not the answer: subtract δ(s) and add δ(t).
- Zero-weight cycles. They are allowed, the seventh test; Dijkstra with a “taken out” mark does not loop on them.
- Unreachable stations. Bellman–Ford from the added vertex gives finite potentials to all vertices, but Dijkstra from a station does not reach them all; then the answer is “*”.
Algorithms behind it
O(V·E + V·(V + E) log V)
2 problems
GRA
Algorithm
The Bellman–Ford algorithm
Shortest paths with negative edges and finding a negative cycle: V rounds over all edges.
O(V · E)
2 problems
GRA
Algorithm
Dijkstra's algorithm
Shortest paths from one vertex in a weighted graph without negative edges.
O((V + E) log V)
3 problems