问题及解答

求下图中每一结点到其他结点的最短路.

首先写出带权邻接矩阵

\[
W=\begin{pmatrix}
0 & 3 & 10 & \infty & \infty & \infty & \infty & \infty\\
3 & 0 & \infty & 5 & \infty & \infty & \infty & \infty\\
10 & \infty & 0 & 6 & \infty & \infty & \infty & \infty\\
\infty & 5 & 6 & 0 & 4& \infty & 10 & \infty\\
\infty & \infty & \infty & 4 & 0 & 9 & 5 & \infty\\
\infty & \infty & \infty & \infty & 9 & 0 & 3 & 4\\
\infty & \infty & \infty & 10 & 5 & 3 & 0 & 6\\
\infty & \infty & \infty & \infty & \infty & 4 & 6 & 0\\
\end{pmatrix}
\]
 

Floyd algorithm
==================
The input matrix is:

--------------------------------
0 3 10 2147483647 2147483647 2147483647 2147483647 2147483647
3 0 2147483647 5 2147483647 2147483647 2147483647 2147483647
10 2147483647 0 6 2147483647 2147483647 2147483647 2147483647
2147483647 5 6 0 4 2147483647 10 2147483647
2147483647 2147483647 2147483647 4 0 9 5 2147483647
2147483647 2147483647 2147483647 2147483647 9 0 3 4
2147483647 2147483647 2147483647 10 5 3 0 6
2147483647 2147483647 2147483647 2147483647 2147483647 4 6 0
--------------------------------

=======FINALLY====================
---Matrix D : ---------
0 3 10 8 12 20 17 23
3 0 11 5 9 17 14 20
10 11 0 6 10 18 15 21
8 5 6 0 4 12 9 15
12 9 10 4 0 8 5 11
20 17 18 12 8 0 3 4
17 14 15 9 5 3 0 6
23 20 21 15 11 4 6 0
---Matrix R : ---------
1 2 3 2 4 7 5 7
1 2 4 4 4 7 5 7
1 4 3 4 4 7 5 7
2 2 3 4 5 7 5 7
4 4 4 4 5 7 7 7
7 7 7 7 7 6 7 8
5 5 5 5 5 6 7 8
7 7 7 7 7 6 7 8
----------------