Single-Source Shortest Paths
Problem statement
Given a directed graph with n vertices numbered 0 through n-1, compute the shortest distance from source to every vertex. Each edge [u,v,w] goes from u to v with nonnegative integer weight w.
Return an array in vertex-number order. The source has distance zero. Return -1 for an unreachable vertex. Parallel edges, self-loops and zero-weight edges are allowed. Distances require signed 64-bit integers.
Function
shortestPaths(n: int, edges: int[][], source: int) → long[]Examples
Example 1
n = 4edges = [[0,1,8],[0,2,1],[2,1,2],[1,3,3],[2,3,10]]source = 0return = [0,3,1,6]The route 0 to 2 to 1 costs 3; continuing to 3 costs 6.
Example 2
n = 3edges = [[1,2,0]]source = 1return = [-1,0,0]Vertex 0 is unreachable and the zero-weight edge reaches vertex 2 at no cost.
Example 3
n = 3edges = [[0,1,1000000000],[1,2,1000000000]]source = 0return = [0,1000000000,2000000000]Distances accumulate edge weights without changing vertex order.
Constraints
1 <= n <= 5000;0 <= edges.length <= 20000.0 <= source,u,v < n;0 <= w <= 1000000000.