Graph Pathfinding or Traversal | Dataford Interview Questions

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):

Your question is Graph Pathfinding or Traversal. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem