#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.
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.
graph.First solves only, ranked by stars and then time.