Editor

Shortest Travel Times

#622 · Graphs · Advanced · Review the AI's code · 140 XP · about 25 min

Someone asked an AI assistant: "Write a function that uses Dijkstra's algorithm to find the shortest travel time from a starting stop to every other stop." This is its answer. It looks right, but it has a bug.

A bus network is a dictionary that maps each stop to a list of (next_stop, minutes) pairs, one for each one-way road leaving it. shortest_times(graph, start) should return a dictionary that maps every stop reachable from start (including start itself, at 0) to the fewest total minutes needed to get there, with the stops in sorted order. Stops that cannot be reached are left out.

Examples

roads = {'A': [('B', 10), ('C', 1)], 'C': [('B', 2)]}
shortest_times(roads, 'A')  # returns {'A': 0, 'B': 3, 'C': 1}
shortest_times(roads, 'C')  # returns {'B': 2, 'C': 0}

Going from A to B directly takes 10 minutes, but going through C takes 1 + 2 = 3.

Constraints

  • Up to 1,000 stops and 5,000 roads; travel times are whole numbers from 0 to 1,000.
  • A stop with no roads leaving it may be missing from graph.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.