In an IBM Cloud service topology, services are connected by directed links with non-negative latency. Given n services labeled 0 to n - 1, a list of weighted directed edges, and a source service source, compute the shortest-path tree rooted at source.
For each node v, return the parent of v in one shortest path from source to v. If v is unreachable, its parent should be -1. The parent of source is also -1. If multiple shortest paths have the same total latency, choose the one whose parent node has the smaller index.
n: integer number of nodesedges: list of [u, v, w] directed edges where u -> v has weight wsource: integer start nodeparent of length n, where parent[v] is the predecessor of v in the shortest-path tree, or -1Example 1
n = 5, edges = [[0,1,2],[0,2,5],[1,2,1],[1,3,2],[2,3,1],[3,4,3]], source = 0[-1, 0, 1, 1, 3]0->1, 0->1->2, 0->1->3, and 0->1->3->4.Example 2
n = 4, edges = [[0,1,1],[0,2,1],[1,3,2],[2,3,2]], source = 0[-1, 0, 0, 1]3 has two shortest paths of total cost 3; choose parent 1 because 1 < 2.1 <= n <= 10^50 <= len(edges) <= 2 * 10^50 <= u, v < n0 <= w <= 10^9