Show problems as
Classic problem #847HardDynamic ProgrammingBit ManipulationBreadth-First SearchGraph TheoryBitmask

Shortest Path Visiting All Nodes

Real-world version: Calling at Every Hub
Tracked in this browser only
Read Shortest Path Visiting All Nodes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A network has hubs numbered 0 through n - 1, and links[i] lists the hubs joined directly to hub i. Every link works both ways, no hub is joined to itself, and every hub can be reached from every other one.

A courier may set off from whichever hub it likes, travels one link at a time, and may pass through any hub as often as it pleases.

Return the fewest links the courier has to cross to have called at every hub.

Examples

Example 1

Input
links = [[1], [0, 2], [1, 3], [2]]
Output
3

The hubs form a single chain, so setting off at one end and walking to the other calls at all four hubs across three links.

Example 2

Input
links = [[1, 2, 3, 4], [0], [0], [0], [0]]
Output
6

Four hubs hang off one middle hub. Setting off from a hanging hub, the courier has to come back through the middle between each pair of them, which is six links.

Example 3

Input
links = [[]]
Output
0

A single hub is already called at, so nothing has to be crossed.

Constraints

  • 1 <= links.length <= 12
  • 0 <= links[i].length < links.length
  • no hub is listed among its own links
  • if hub b is listed for hub a then hub a is listed for hub b
  • every hub can be reached from every other one

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_path_length(links: list[list[int]]) -> int:
Java
public int shortestPathLength(int[][] links)

More on the same topics