Shortest travel time to every stop in a weighted graph
A city transit app shows riders how long it takes to reach every stop from where they are. The network is a directed graph: each connection has a travel time in minutes, and some connections run only one way.
Implement shortestTravelTimes(graph, source). It returns the minimum travel time from source to every stop in the network.
shortestTravelTimes(graph, source) // => { [stop]: minutes }
graph is an object. Each key is a stop name and its value is an object mapping each directly reachable stop to the travel time in minutes: { Harbor: { Market: 4 } } means a one-way connection from Harbor to Market that takes 4 minutes.source is a stop name. It may not appear in graph at all.graph, every destination, and source.source. source itself is 0.Infinity.RangeError if any travel time is negative, NaN, infinite, or not a number.0 are allowed. The network can contain cycles.graph.const network = {
Harbor: { Market: 4, Museum: 9 },
Market: { Museum: 3, Stadium: 11 },
Museum: { Stadium: 2 },
Airport: { Harbor: 30 },
};
shortestTravelTimes(network, 'Harbor');
// => { Harbor: 0, Market: 4, Museum: 7, Stadium: 9, Airport: Infinity }
// Museum: Harbor → Market → Museum (4 + 3) beats the direct 9.
// Airport has an outgoing connection only, so it cannot be reached.
shortestTravelTimes(network, 'Stadium');
// => { Harbor: Infinity, Market: Infinity, Museum: Infinity, Stadium: 0, Airport: Infinity }
shortestTravelTimes({ A: { B: 1 } }, 'Depot');
// => { A: Infinity, B: Infinity, Depot: 0 }
shortestTravelTimes({ A: { B: -2 } }, 'A'); // throws RangeError