Graphs · pattern 7 of 8

Weighted shortest path

Searching level by level finds the fewest links. When links have different costs, a route with more links can be cheaper, so that is not enough. Keep the best cost known for each place, and check every link in rounds until no cost improves.

Watch it run in the app

When to use it

Use it when every link has its own cost and you need the cheapest route from one start to another place, or to every place.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A courier rides between 5 towns, numbered 0 to 4. Each road [a, b, minutes] can be ridden in both directions and takes that many minutes. Return the fewest minutes needed to ride from town start to town end, or -1 if there is no way.

Input
n = 5
roads = [[0, 1, 6], [0, 2, 2], [0, 4, 12], [1, 4, 4], [1, 2, 3], [2, 3, 8], [3, 4, 1]]
start = 0
end = 4

Output
9

The method

Write each road as two one-way links
No town has a time yet, except the start at 0
Run up to n - 1 rounds; each one checks every link
A link gives a shorter time: store it and note a change
A round changes nothing: every time is final, so stop
Return the end's time, or -1 if it was never reached

The run, one moment at a time

Step 1. The map has 5 towns and 7 roads, each marked with its minutes. A road can be ridden both ways, so it is written as two one-way links: 14 links in all.
```
minutes: ∞ ∞ ∞ ∞ ∞
```
Step 2. Town 0 is the start, 0 minutes away. No way to the other towns is known yet, which is shown as ∞. The row holds the best time known so far for each town.
```
minutes: 0 ∞ ∞ ∞ ∞
```
Step 4. Round 1 checks the 14 links in the order of the list. Link 0 to 1: 0 + 6 = 6 beats ∞. Store 6 for town 1, and note that a time changed.
```
minutes: 0 6 ∞ ∞ ∞
round: 1
changed: yes
```
Step 3. The same road the other way, link 1 to 0: 6 + 6 = 12 does not beat the 0 of town 0, so nothing is stored. From now on only links that lower a time are shown.
```
minutes: 0 6 ∞ ∞ ∞
round: 1
changed: yes
```
Step 4. Link 0 to 2: 0 + 2 = 2 beats ∞. Store 2 for town 2.
```
minutes: 0 6 2 ∞ ∞
round: 1
changed: yes
```
Step 4. Link 0 to 4, the direct road: 0 + 12 = 12 beats ∞. Store 12 for town 4. A way over more roads may still be faster.
```
minutes: 0 6 2 ∞ 12
round: 1
changed: yes
```
Step 4. Link 1 to 4: 6 + 4 = 10 beats the 12 of the direct road. Store 10 for town 4. A stored time is only the best known so far.
```
minutes: 0 6 2 ∞ 10
round: 1
changed: yes
```
Step 4. Link 2 to 1: 2 + 3 = 5 beats 6. Store 5 for town 1. Link 1 to 4 was checked before this, with the old 6.
```
minutes: 0 5 2 ∞ 10
round: 1
changed: yes
```
Step 4. Link 2 to 3: 2 + 8 = 10 beats ∞. Store 10 for town 3.
```
minutes: 0 5 2 10 10
round: 1
changed: yes
```
Step 4. Round 1 changed some times, so round 2 checks every link again. Link 1 to 4: 5 + 4 = 9 beats 10. Store 9 for town 4.
```
minutes: 0 5 2 10 9
round: 2
changed: yes
```
Step 5. Round 2 lowered one time, so round 3 runs. No link lowers a time in it: every time is final, so stop. A fastest way through 5 towns has at most 4 roads, so 4 rounds are always enough.
```
minutes: 0 5 2 10 9
round: 3
changed: no
```
Step 6. The fastest ride takes 9 minutes over 3 roads: 0 to 2 to 1 to 4. The direct road is 1 road and takes 12 minutes. The fewest roads is not the fastest way.
```
minutes: 0 5 2 10 9
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(n, roads, start, end) {
  // 1. Write each road as two one-way links
  const links = [];
  for (const [a, b, minutes] of roads) {
    links.push([a, b, minutes]);
    links.push([b, a, minutes]);
  }
  // 2. No town has a time yet, except the start at 0
  const best = Array(n).fill(Infinity);
  best[start] = 0;
  // 3. Run up to n - 1 rounds; each one checks every link
  // A fastest way has at most n - 1 links, so that is enough.
  for (let round = 1; round < n; round++) {
    let changed = false;
    for (const [town, other, minutes] of links) {
      // 4. A link gives a shorter time: store it and note a change
      if (best[town] + minutes < best[other]) {
        best[other] = best[town] + minutes;
        changed = true;
      }
    }
    // 5. A round changes nothing: every time is final, so stop
    if (!changed) break;
  }
  // 6. Return the end's time, or -1 if it was never reached
  return best[end] === Infinity ? -1 : best[end];
}

Python

def solve(n, roads, start, end):
    # 1. Write each road as two one-way links
    links = []
    for a, b, minutes in roads:
        links.append((a, b, minutes))
        links.append((b, a, minutes))
    # 2. No town has a time yet, except the start at 0
    best = [float("inf")] * n
    best[start] = 0
    # 3. Run up to n - 1 rounds; each one checks every link
    # A fastest way has at most n - 1 links, so that is enough.
    for _ in range(n - 1):
        changed = False
        for town, other, minutes in links:
            # 4. A link gives a shorter time: store it and note a change
            if best[town] + minutes < best[other]:
                best[other] = best[town] + minutes
                changed = True
        # 5. A round changes nothing: every time is final, so stop
        if not changed:
            break
    # 6. Return the end's time, or -1 if it was never reached
    return -1 if best[end] == float("inf") else best[end]

How to spot it

Given: Each road has its own length, time or price: Counting links is wrong when costs differ: three cheap links can beat one costly link. The costs must be added along each route.
Asked: The cheapest, shortest or fastest way from a start: The answer is the smallest sum of costs along a route from the start. Keep the best sum known for each place and lower it link by link.
Asked: The cheapest route that uses at most k links: Let each round read only the costs from before it, kept in a copy. Then a round lets every route grow by one link, so run k rounds.

Looks like it, but is not

Every step costs the same, and you need the fewest steps. Use Breadth-first search by distance. With equal costs the fewest links is also the cheapest. A queue reaches each place once, nearest first, so no rounds are needed.
You must join all the places as cheaply as possible, not travel between two of them. Use Minimum spanning tree. That compares the cost of one link alone. A shortest path compares the whole cost from the start, so different links can win.
You only need to know whether a place can be reached at all. Use Graph traversal with a visited set. Costs do not change what can be reached. A plain walk that marks visited places answers it with less work.

Cost and mistakes

A cheapest route has at most n - 1 links, so n - 1 rounds are enough, each checking all m links: at most n times m steps, written O(n * m). Extra space is the list of links and one cost for each place.

Watch out

One pass over the links is not enough. A cost can improve after the links that leave its place were checked, so repeat the pass until a whole round changes nothing.
Rounds, the Bellman-Ford method, get slow on a large map. When no cost is below zero, a faster method, Dijkstra's, always finishes the closest unfinished place next, taken from a heap. The solutions of the 150 use rounds.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 2

Network Delay TimeMedium · Advanced Graphs
Cheapest Flights Within K StopsMedium · Advanced Graphs