Optimal Path Function | Dataford Interview Questions

Write a function to determine the optimal path in a given data structure.

Treat the data structure as a directed weighted graph with nonnegative edge weights. Implement def optimal_path(graph, start, target):, where graph maps each node to a list of [neighbor, weight] pairs. Return {"path": [...], "cost": number} for the minimum-cost route, or None when the target is unreachable. If start == target, return a zero-cost path containing only start.

Constraints

1 <= number of nodes <= 10^4
0 <= number of directed edges <= 10^5
All edge weights are nonnegative integers
Each adjacency entry has the form [neighbor, weight]
Node identifiers are hashable and consistent across the graph
Return any minimum-cost path when multiple paths have the same cost

Function Signature

def optimal_path(graph, start, target):

Your question is Optimal Path Function. 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

Write a function to determine the optimal path in a given data structure.

Constraints

1 <= number of nodes <= 10^4
0 <= number of directed edges <= 10^5
All edge weights are nonnegative integers
Each adjacency entry has the form [neighbor, weight]
Node identifiers are hashable and consistent across the graph
Return any minimum-cost path when multiple paths have the same cost

Function Signature

def optimal_path(graph, start, target):

Your question is Optimal Path Function. 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.