Floyd-Warshall (FW) - Classic Problems | Repovive

CLS16. Floyd-Warshall (FW)

1s256 MB

Given a weighted directed graph with $n$ vertices and $m$ edges, find the shortest distance between every pair of vertices.

Edge weights are non-negative. If there is no path from vertex $i$ to vertex $j$ , the distance is $-1$ .

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

\begin{array}{cccc} d_{1,1} & d_{1,2} & \cdots & d_{1,n} \\ d_{2,1} & d_{2,2} & \cdots & d_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{n,1} & d_{n,2} & \cdots & d_{n,n} \end{array}

d_{i,j} = \begin{cases} \text{shortest distance from } i \text{ to } j & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 0 3 5 6 5 0 2 3 3 6 0 1 2 5 7 0.

Output

Input

Explanation

For this input, the required output is 0 1 3 -1 0 2 -1 -1 0.

Output

0 1 3
-1 0 2
-1 -1 0

Input

2 0

Explanation

For this input, the required output is 0 -1 -1 0.

Output

0 -1
-1 0

Given a weighted directed graph with $n$ vertices and $m$ edges, find the shortest distance between every pair of vertices.

Edge weights are non-negative. If there is no path from vertex $i$ to vertex $j$ , the distance is $-1$ .

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

\begin{array}{cccc} d_{1,1} & d_{1,2} & \cdots & d_{1,n} \\ d_{2,1} & d_{2,2} & \cdots & d_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{n,1} & d_{n,2} & \cdots & d_{n,n} \end{array}

d_{i,j} = \begin{cases} \text{shortest distance from } i \text{ to } j & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}