Shortest Path in Dependency Graph | Dataford Interview Questions

Write a function to find the shortest path between two nodes in an integration dependency graph.

Represent the graph as a directed adjacency dictionary where each node maps to [neighbor, cost] pairs, with nonnegative costs. Return the node sequence for a minimum-cost path, or [] when no path exists; if the start and destination are identical, return [start].

Constraints

1 <= number of nodes <= 5000
0 <= number of directed edges <= 20000
Each edge is represented as [neighbor, cost]
All edge costs are nonnegative integers
Node identifiers are strings
The graph may contain cycles
Return any minimum-cost path when multiple paths have the same cost

Function Signature

def shortest_path(graph, start, end):

Your question is Shortest Path in Dependency Graph. 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 find the shortest path between two nodes in an integration dependency graph.

Constraints

1 <= number of nodes <= 5000
0 <= number of directed edges <= 20000
Each edge is represented as [neighbor, cost]
All edge costs are nonnegative integers
Node identifiers are strings
The graph may contain cycles
Return any minimum-cost path when multiple paths have the same cost

Function Signature

def shortest_path(graph, start, end):

Your question is Shortest Path in Dependency Graph. 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.