1078. Johnson's Algorithm — All-Pairs on Sparse Graph

Given a directed weighted graph with n nodes and edges [u, v, w] (weights may be negative but with no negative cycle), return the all-pairs shortest-path matrix using Johnson's algorithm. Entry [i][j] is the shortest distance from i to j (0 on the diagonal, null where no path exists). The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, w].

Output: Nested array — the all-pairs distance matrix (null where unreachable).

Examples

Input: {"n":3,"edges":[[0,1,4],[0,2,1],[2,1,-2]]}
Output: [[0,-1,1],[null,0,null],[null,-2,0]]
Explanation: Reweighted shortest paths.

Input: {"n":1,"edges":[]}
Output: [[0]]
Explanation: Single node.

Input: {"n":2,"edges":[[0,1,3]]}
Output: [[0,3],[null,0]]
Explanation: One directed edge.

Constraints

• 1<=n<=500
• no negative cycle

Asked by