Free Graphs lessonsGraphs · Stage 5 · Shortest paths · Step 1

Not just how far, but which way

Remember who discovered each place, then walk backwards from the target to read off the actual route. About 14 minutes.

Leave a note when you discover someone

A search tells you how far each place is, but not the route. The fix is cheap. When the search first reaches a place from some neighbour, write down that neighbour as the place's parent. A place is discovered only once, so it only ever gets one parent.

The start has no parent, so give it -1. And a place whose parent is still unset (we use -2 for that) was never reached, which doubles as the unreached marker.

Parent: is who discovered you first.

Only once: the first discovery wins; later ones are skipped.

In code

parent = {start: None}
parent[nxt] = node       # who found it

Shortest route from 0 to 5. The small numbers are parents.

Start at 0. Its parent is -1 because nobody discovered it.

Move 1 of 4

Walk back, then flip

Once the search is done, stand on the target and follow parent notes: target, its parent, that parent's parent, until you reach the start. That gives the route backwards, so reverse it at the end.

If several routes are equally short, which one do you get? To make it the same every time, sort each place's neighbours from smallest to largest before searching. Then the route you get is the alphabetically first among the shortest ones.

Backwards then flip: walk from the target, then reverse.

Sorted neighbours: make the choice among equal routes predictable.

In code

path = []
while node is not None:
    path.append(node)
    node = parent[node]
path.reverse()

Quick check

While walking back from the target you reach a place whose parent is -1. What does that tell you?

AIt is the start, so the route is complete
BThe target cannot be reached
CSomething went wrong and you should start again

Show the answer

It is the start, so the route is complete. Only the start has no discoverer, so the walk ends there.

Your problem

The shortest route itself

There are n places, numbered 0 to n − 1, joined by two-way roads. edges[i] = [a, b] means a road between place a and place b. Return the list of places on a route from start to target that uses the fewest roads, in order, including both ends. If more than one such route exists, return the one that is smallest when compared place by place (so a route that begins 0, 1 beats one that begins 0, 2). If target can't be reached, return an empty list.

Example

n = 6, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [2, 5], [4, 5]], start = 0, target = 5 → [0, 2, 5]

1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000

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