DSA Factory
Free Graphs lessonsGraphs · Stage 6 · Weighted paths · Step 1

Roads that cost different amounts

Find the cheapest route when roads have different prices, by always settling the cheapest unfinished place next. About 16 minutes.

Settle the cheapest first

Dijkstra's idea: keep the best known price to every place, starting with 0 for the start and infinity for the rest. Then repeat the same move. Pick the open place with the lowest price and settle it, which means its price is now final.

Then look at its roads. For each neighbour, check whether going through this place makes the neighbour cheaper. If so, update the price. The place you settle next is again the cheapest one still open.

Settle: the cheapest open place; its price is final.
Relax: lower neighbours' prices if this way is cheaper.
In code
heap = [(0, start)]
d, node = heappop(heap)
heappush(heap, (d + w, nxt))
Cheapest trip from 0 to 4. Numbers on roads are prices, numbers under places are the best price so far.
412153001234
heap
[0 at place 0]

Start at 0 with price 0. Everything else is unknown (infinity).

Move 1 of 5

Why a heap, and why skip

Finding the cheapest open place by scanning every place each time is slow. A min-heap keeps the open places so that the cheapest is always on top.

A place can be pushed more than once as its price improves. That's fine: when you pop an old, higher entry, its price is worse than the best known, so skip it. This only works if no road has a negative price, because a negative road could make an already-settled place cheaper later.

Stale entry: if its price is above the best known, skip it.
No negative roads: or settled prices could change.
Quick check

Place A is the cheapest open place, with price 5, and a road of price 2 leads from A to B, whose price is 9. What happens to B?

  1. AB's price drops to 7, because 5 + 2 is less than 9
  2. BB stays at 9, since it was found first
  3. CB's price becomes 14
Show the answer

B's price drops to 7, because 5 + 2 is less than 9. Going through A is cheaper, so B's best known price improves.

Your problem

Cheapest route

There are n places, numbered 0 to n − 1, joined by two-way roads. roads[i] = [a, b, w] is a road between place a and place b that costs w to travel, where w is at least 1. Return the smallest total cost of getting from place start to place target, or -1 if it can't be done.

Example
n = 5, roads = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]], start = 0, target = 4 → 7

1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000 · 1 ≤ w ≤ 1,000 · the answer fits in a 32-bit integer

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve