Find Minimum Travel Time and Route

MediumPython

Problem

An eBay fulfillment service models delivery connections as a directed weighted graph. Each node is a fulfillment location, and each edge contains the travel time between two locations. Given a starting location and a destination, find the minimum travel time and one corresponding route.

Formal Specification

Implement minimum_delivery_time(graph, start, destination).

graph is a dictionary mapping a node ID to a list of [neighbor, travel_time] pairs.
start and destination are node ID strings present in the graph.
Travel times are positive integers.
Return [minimum_time, path], where path is a list of node IDs from start to destination.
If the destination cannot be reached, return [-1, []].

Constraints

1 <= number of nodes <= 10^5
0 <= number of edges <= 2 * 10^5
1 <= travel_time <= 10^6
Node IDs are unique strings.
All travel times are positive.
The graph may contain cycles and parallel edges.

Function Signature

def minimum_delivery_time(graph, start, destination):

Formal Specification

Implement minimum_delivery_time(graph, start, destination).

graph is a dictionary mapping a node ID to a list of [neighbor, travel_time] pairs.
start and destination are node ID strings present in the graph.
Travel times are positive integers.
Return [minimum_time, path], where path is a list of node IDs from start to destination.
If the destination cannot be reached, return [-1, []].