Shortest Path in a Graph | Dataford Interview Questions

You are given a directed graph with non-negative edge weights. Write a function that returns the shortest distance from a start node to an end node, along with the actual path taken.

If the end node is unreachable, return (-1, []).

Formal Specification

Input:
- n, the number of nodes labeled 0 to n - 1
- edges, a list of [u, v, w] triples representing a directed edge from u to v with weight w
- start, the source node
- end, the destination node
Output:
- A tuple (distance, path) where distance is the minimum total weight from start to end, and path is a list of node labels from start to end

Use an algorithm that is efficient for sparse graphs and handles up to large input sizes.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
0 <= u, v < n
0 <= w <= 10^9
0 <= start, end < n
All edge weights are non-negative

Function Signature

def shortest_path(n, edges, start, end):

Your question is Shortest Path in a 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