Warshall a b c d e
a 0 1 0 0 0
b 0 0 1 0 0
c 0 0 0 1 0
d 1 0 0 0 1
e 0 0 0 0 0

$R_{ij} = R_{ik} \cup R_{kj}$

$R^1$

Warshall a b c d e
a 1 1 1 1 1
b 1 1 1 1 1
c 1 1 1 1 1
d 1 1 1 1 1
e 0 0 0 0 0

Floyd是可以算图中任意两个点的最短路径

1

Warshall a b c d e
a 0 5 $$\infty$$ $$\infty$$ $$\infty$$
b $$\infty$$ 0 2 $$\infty$$ $$\infty$$
c $$\infty$$ $$\infty$$ 0 1 $$\infty$$
d 6 15 $$\infty$$ 0 1
e $$\infty$$ $$\infty$$ $$\infty$$ $$\infty$$ 0

$R_{ij}=min\{R_{ij},R_{ik}+R_{kj}\}$