Shortest Path With Negative Weights
You are given n cities labeled 0 to n - 1 and a list of directed edges edges, where edgesi = [u, v, w] means a road from city u to city v with cost w. Costs can be negative, but the graph has no negative-weight cycle reachable from the source. Given a source city src, return an array dist where disti is the cheapest cost from src to city i, or -1 if city i is unreachable. Relax every edge n - 1 times : that many full passes is always enough for a shortest path to be found, because the longest possible shortest path uses at most n - 1 edges.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ edges.length ≤ 500
- edgesi.length == 3
- 0 ≤ u, v ≤ n - 1
- -1000 ≤ w ≤ 1000
- 0 ≤ src ≤ n - 1
- no negative-weight cycle is reachable from src
Example
n = 4, edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 2]], src = 0[0, 4, 1, 3]Explanation The cheapest route to city 2 goes 0 → 1 → 2, costing 4 + (-3) = 1, which beats the direct edge cost of 5.
In plain terms
- Relax an edge
- Check whether going through this edge gives a cheaper route to its destination than what you already have, and if so, update it.
- Negative-weight cycle
- A loop of edges whose total cost is negative, so walking it over and over keeps lowering the cost forever — this problem's graph doesn't have one reachable from src.
Relax every edge, pass after pass, until nothing improves
dist[0] = 0 (the source); every other city starts at infinity.
What happens in this step
pass 1 begins dist[0] = 0 (source) dist[1] = dist[2] = dist[3] = ∞ Only the source starts at a known distance; every other city is unreachable until an edge proves otherwise. Bellman-Ford will now scan all 4 edges, up to n - 1 = 3 times.
Steps to visualize
- Set distsrc = 0 and every other disti = infinity.
- Walk the edge list in order; for each edge (u, v, w), if distu + w is cheaper than distv, update distv.
- Repeat the full edge list scan up to n - 1 times.
- If a full pass makes no changes, the distances have already converged and the algorithm can stop early.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
dist[0] = 0 (the source); every other city starts at infinity.
What happens in this step
pass 1 begins dist[0] = 0 (source) dist[1] = dist[2] = dist[3] = ∞ Only the source starts at a known distance; every other city is unreachable until an edge proves otherwise. Bellman-Ford will now scan all 4 edges, up to n - 1 = 3 times.
Solution
function shortestPathWithNegativeWeights(n, edges, src) {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (let i = 0; i < n - 1; i++) {
let changed = false;
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
changed = true;
}
}
if (!changed) break;
}
return dist.map((d) => (d === Infinity ? -1 : d));
}- Time
- O(n * e)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 4, edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 2]], src = 0 | [0, 4, 1, 3] | example from the docstring |
n = 4, edges = [[0, 1, 2], [2, 3, 1]], src = 0 | [0, 2, -1, -1] | cities with no incoming path from src stay marked unreachable |
n = 2, edges = [[0, 1, -5]], src = 0 | [0, -5] | a single negative edge with no cycle risk |
n = 3, edges = [[1, 2, 3]], src = 0 | [0, -1, -1] | src has no outgoing edges at all |
n = 3, edges = [[0, 1, 5], [0, 1, 2], [1, 2, 1]], src = 0 | [0, 2, 3] | two parallel edges between the same pair of cities, cheaper one wins |
n = 5, edges = [[3, 4, 1], [2, 3, 1], [1, 2, 1], [0, 1, 1]], src = 0 | [0, 1, 2, 3, 4] | edges listed out of order so the update needs the full n - 1 passes to propagate |
n = 1, edges = [], src = 0 | [0] | smallest valid input, a single city and no edges |