Route Planning From A to B | Dataford Interview Questions

Could you tell us how to get from route A to route B, and how you would optimize the best path?

Implement the solution for a directed, weighted graph whose edge weights are nonnegative. Return the minimum-cost path and its total cost from start to end. If no route exists, return an empty path and None.

Function signature: find_best_route(graph, start, end)

graph maps each node to a list of [neighbor, cost] pairs. The result must be a dictionary with path and cost keys.

Constraints

1 <= number of nodes <= 1000
0 <= number of edges <= 10000
Edge costs are nonnegative integers
Node identifiers are strings
The graph is directed
The input graph may omit nodes with no outgoing edges

Function Signature

def find_best_route(graph, start, end):

Your question is Route Planning From A to B. 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