Print a Shortest Graph Path
Amazon● MediumFULLTIMEONSITE INTERVIEWProblem statement
Given n vertices and directed edges, return the lexicographically smallest vertex sequence among all shortest paths from source to target.
Function
shortestPath(n: int, edges: int[][], source: int, target: int) → int[]Examples
Example 1
n = 5edges = [[0,1],[0,2],[1,4],[2,4]]source = 0target = 4return = [0,1,4]Both paths have two edges, and the path through one is lexicographically smaller.
Example 2
n = 4edges = [[0,1]]source = 0target = 3return = []The target is unreachable.
Constraints
1 <= n <= 100000- Edges contain valid vertex indices.
- Duplicate edges and self-loops may appear.