某公司在六个城市 $C_1,C_2,C_3,C_4,C_5,C_6$ 中都有分公司. 从 $C_i$ 到 $C_j$ 的直达航班票价由下述矩阵的第 $i$ 行、第 $j$ 列元素给出 ($\infty$ 表示无直达航班).
该公司希望计算出一张任意两个城市之间最廉价路线表, 试作出这样的表来.
\[
\begin{pmatrix}
0 & 50 & \infty & 40 & 25 & 10\\
50 & 0 & 15 & 20 & \infty & 25\\
\infty & 15 & 0 & 10 & 20 & \infty\\
40 & 20 & 10 & 0 & 10 & 25\\
25 & \infty & 20 & 10 & 0 & 55\\
10 & 25 & \infty & 25 & 55 & 0\\
\end{pmatrix}
\]
1
通过使用 Floyd.exe 进行计算
Floyd algorithm
==================
The input matrix is:
--------------------------------
0 50 2147483647 40 25 10
50 0 15 20 2147483647 25
2147483647 15 0 10 20 2147483647
40 20 10 0 10 25
25 2147483647 20 10 0 55
10 25 2147483647 25 55 0
--------------------------------
Result:
---Matrix D : ---------
0 35 45 35 25 10
35 0 15 20 30 25
45 15 0 10 20 35
35 20 10 0 10 25
25 30 20 10 0 35
10 25 35 25 35 0
---Matrix R : ---------
1 6 5 5 5 6
6 2 3 4 4 6
5 2 3 4 5 4
5 2 3 4 5 6
1 4 3 4 5 1
1 2 4 4 1 6
----------------