DSA sheet / Graph
Shortest Routes I
Do these first: Message Route
The problem in brief
There are n cities (up to 100 000) and m one-way flights (up to 200 000), each with a positive length up to 10^9. Print the length of the shortest route from city 1 to each city 1..n.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1671.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
BFS breaks down as soon as edges have different costs. What property of positive weights can you exploit to know a node’s distance is final?
-
If you always settle the not-yet-settled node with the smallest tentative distance, can a later path ever beat it? Why does positivity matter?
-
How do you repeatedly find the smallest tentative distance quickly, given that distances keep improving? Think of a priority queue with lazy deletion.
-
What is the largest possible answer, and which integer type holds it?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
This is single-source shortest paths with non-negative weights: the domain of Dijkstra’s algorithm. The brute-force alternative, trying every path, is exponential, and Bellman-Ford (relax all edges n times) is O(n * m), too slow at this size. Dijkstra works because of one invariant: the unsettled node with the smallest tentative distance has that distance final, since any other route to it would have to pass through some unsettled node with an even larger tentative distance and then add non-negative cost. This is exactly why the algorithm breaks with negative edges.
Implementation choices matter. A min-heap keyed by distance gives O((n + m) log n). Instead of decreasing keys, push a new (distance, node) pair whenever you improve a distance and skip stale pairs when you pop them (if popped distance is larger than the stored one, ignore). The habit: when a problem has weights, the first question is “are they non-negative?”, and that decides Dijkstra versus Bellman-Ford.
Intuition
Imagine cities lighting up in order of how cheaply you can reach them. The next city to light up is always the cheapest of all cities adjacent to the lit region. When a city lights up its outgoing flights offer new, possibly cheaper prices to its neighbours.
Approach
- dist[1] = 0, all others infinity; push (0, 1) on a min-heap.
- Pop the smallest (d, u). If d > dist[u], skip it (stale). Otherwise for each flight u -> v with price w: if d + w < dist[v], update dist[v] and push (dist[v], v).
- When the heap is empty, print dist[1..n]. The code below assumes every city can be reached from city 1 (the statement does not spell this out, so this sheet assumes every test is reachable); on an input with an unreachable city these programs would print their infinity marker, so decide what to print there before relying on them.
Pitfalls: distances can reach about 10^5 * 10^9 = 10^14, so use 64-bit; edges are directed, so add each only one way; use adjacency lists; in JavaScript there is no built-in heap, so the version below includes a small binary heap.
Complexity
O((n + m) log m) time, O(n + m) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
long long w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
}
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
for (int v = 1; v <= n; v++) cout << dist[v] << (v < n ? ' ' : '\n');
return 0;
}import sys
import heapq
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
a = int(data[2 + 3 * i])
b = int(data[3 + 3 * i])
w = int(data[4 + 3 * i])
adj[a].append((b, w))
INF = float('inf')
dist = [INF] * (n + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
print(" ".join(str(dist[v]) for v in range(1, n + 1)))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int m = (int) st.nval;
int[] head = new int[n + 1];
Arrays.fill(head, -1);
int[] next = new int[m];
int[] to = new int[m];
long[] cost = new long[m];
for (int e = 0; e < m; e++) {
st.nextToken();
int a = (int) st.nval;
st.nextToken();
to[e] = (int) st.nval;
st.nextToken();
cost[e] = (long) st.nval;
next[e] = head[a];
head[a] = e;
}
final long INF = Long.MAX_VALUE / 4;
long[] dist = new long[n + 1];
Arrays.fill(dist, INF);
dist[1] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
pq.add(new long[] {0, 1});
while (!pq.isEmpty()) {
long[] top = pq.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue; // stale entry
for (int e = head[u]; e != -1; e = next[e]) {
long nd = top[0] + cost[e];
if (nd < dist[to[e]]) {
dist[to[e]] = nd;
pq.add(new long[] {nd, to[e]});
}
}
}
StringBuilder sb = new StringBuilder();
for (int v = 1; v <= n; v++) sb.append(dist[v]).append(v < n ? ' ' : '\n');
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const m = data[1];
const adj = Array.from({ length: n + 1 }, () => []);
for (let i = 0; i < m; i++) adj[data[2 + 3 * i]].push([data[3 + 3 * i], data[4 + 3 * i]]);
// Minimal binary min-heap of [distance, node] pairs (JavaScript has no built-in priority queue).
const heap = [];
function push(item) {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
}
function pop() {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1;
const r = l + 1;
let s = i;
if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
}
const dist = new Array(n + 1).fill(Infinity);
dist[1] = 0;
push([0, 1]);
while (heap.length > 0) {
const [d, u] = pop();
if (d > dist[u]) continue; // stale entry
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
push([dist[v], v]);
}
}
}
console.log(dist.slice(1).join(' '));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).