当前位置：首页 > news >正文

数据结构：以一个例题演示弗洛伊德算法

news 来源：原创 2025/8/9 21:24:53

例 8.5.2 利用弗洛伊德算法，对图 8.5.5 中左侧的带权有向图求最短路径，给出每一对顶点之间的最短路径及其路径长度在求解过程中的变化。

在这里插入图片描述

图 8.5.5 带权图和邻接矩阵

【解】

根据图 8.5.5 中的带权有向图，可得所对应的邻接矩阵 $g$ ，如图 8.5.5 右侧图所示。

根据弗洛伊德算法，所对应的 $4\times 4$ 的矩阵序列是： $\pmb{A}_{-1},\pmb{A}_0,\pmb{A}_1,\pmb{A}_2,\pmb{A}_3~(n=4)$ 。

（1） $A−1 \pmb{A}_{-1}$ ，不经过任何中间结点，任何两个顶点之间的距离，即为邻接矩阵
$\begin{split} \pmb{A}_{-1}=g=\begin{bmatrix}0&1&\infty&4\\\infty&0&9&2\\3&5&0&8\\\infty&\infty&6&0 \end{bmatrix} \end{split}$
用矩阵 $\text{path}_{-1}$ 保存此时的最短路径，注意，此时意味着两个顶点之间是否有直接地、不经过中间顶点的路径。如果顶点 $i$ 和顶点 $j$ 之间有路径，则 $\pmb{path}_{-1}[i][j]=i$ ，否则 $\pmb{path}_{-1}[i][j]=-1$ 。

元素 $\pmb{A}_{-1}[0][0]$ （下标按照图 3 右侧的邻接矩阵方式表示），说明顶点 0 到顶点 0 没有路径，则 $\pmb{path}_{-1}[0][0]=-1$ 。
元素 $\pmb{A}_{-1}[0][1]=1$ ，说明顶点 0 到顶点 1 的路径权值是 1 ，有路径，则 $\pmb{path}_{-1}[0][1]=0$ 。
元素 $\pmb{A}_{-1}[0][2]=\infty$ ，说明顶点 0 到顶点 2 没有路径，则 $\pmb{path}_{-1}[0][2] =-1$ 。
$\cdots$

用上述方法，即可得到矩阵 $path−1 \pmb{path}_{-1}$ 。具体实现的时候，可以按照行号观察 $A−1 \pmb{A}_{-1}$ ，在某一行中，其元素非 $0$ 或者非 $\infty$ ，则说明该行号到所对应列有路径，那么对应到 $path−1 \pmb{path}_{-1}$ 中的相应位置元素即为 $A−1 \pmb{A}_{-1}$ 中的该行的行号；否则为 $- 1$ 。所以得到矩阵 $path−1 \pmb{path}_{-1}$ 如下：
$\pmb{path}_{-1}=\begin{bmatrix}-1&0&-1&0\\-1&-1&1&1\\2&2&-1&2\\-1&-1&3&-1\end{bmatrix}$
（2） $A0 \pmb{A}_0$ ，以顶点 0 为中间点，任何两个顶点之间的最短距离，即 $\pmb{A}_0[i,j]=\min(\pmb{A}_{-1}[i,j],\pmb{A}_{-1}[i,0])+\pmb{A}_{-1}[0,j])$ 。
$\begin{split} &\pmb{A}_0[0,0] = 0 \\&\pmb{A}_0[0,1]=\min(\pmb{A}_{-1}[0,1],\pmb{A}_{-1}[0,0]+\pmb{A}_{-1}[0,1])=1 \\&\pmb{A}_0[0,2]=\min(\pmb{A}_{-1}[0,2],\pmb{A}_{-1}[0,0]+\pmb{A}_{-1}[0,2])=\infty \\&~\vdots \\&\pmb{A}_0[2,1]=\min(\pmb{A}_{-1}[2,1],\pmb{A}_{-1}[2,0]+\pmb{A}_{-1}[0,1])=4 \\&~\vdots \end{split}$
最终得到 $A0 \pmb{A}_0$ 如下：
$\pmb{A}_0=\begin{bmatrix}0&1&\infty&4\\\infty&0&9&2\\3&4&0&7\\\infty&\infty&6&0\end{bmatrix}$
如果 $\pmb{A}_0[i,j]=\pmb{A}_1[i,j]$ ，则说明路径没有调整，即 $\pmb{path}_0[i,j]=\pmb{path}_{-1}[i,j]$ 。

否则，路径已经调整，即：经过顶点 $k$ 的路径较短，则 $\pmb{A}_k[i][j]=\pmb{A}_{k-1}[i][k]+\pmb{A}_{k-1}[k][j]$ ， $\text{path}_k[i][j]=a=\text{path}_{k-1}[k][j]$ ，所以有： $\pmb{path}_0[i,j]=\pmb{path}_{-1}[0,j]$ 。

由以上规则，可得矩阵 $path \pmb{path}$ ：
$\pmb{path}_{0}=\begin{bmatrix}-1&0&-1&0\\-1&-1&1&1\\2&0&-1&0\\-1&-1&3&-1\end{bmatrix}$
（3） $A1 \pmb{A}_1$ ，以顶点 1 为中间点，任何两点之间的最短距离，即 $\pmb{A}_1[i,j]=\min(\pmb{A}_0[i,j],\pmb{A}_0[i,1]+\pmb{A}_0[1,j])$ 。
$\begin{split} &\pmb{A}_1[0,0]=0 \\&\pmb{A}_1[0,1]=\min(\pmb{A}_0[0,1],\pmb{A}_0[0,1]+\pmb{A}_0[1,1])=1 \\&\pmb{A}_1[0,2]=\min(\pmb{A}_0[0,2],\pmb{A}_0[0,1]+\pmb{A}_0[1,2])=10 \\&\pmb{A}_1[0,3]=\min(\pmb{A}_0[0,3],\pmb{A}_0[0,1]+\pmb{A}_0[1,3])=3 \\&\pmb{A}_1[1,0]=\min(\pmb{A}_0[1,0],\pmb{A}_0[1,1]+\pmb{A}_0[1,0])=\infty \\~&\vdots \end{split}$
最终得到：
$\pmb{A}_1=\begin{bmatrix}0&1&10&3\\\infty&0&9&2\\3&4&0&6\\\infty&\infty&6&0\end{bmatrix}$
比较 $A1 \pmb{A}_1$ 和 $A0 \pmb{A}_0$ ，若相等，则 $\pmb{path}_1[i,j]=\pmb{path}_0[i,j]$ ，否则 $\pmb{path}_1[i,j]=\pmb{path}_0[1,j]$ ，由此得到：
$\pmb{path}_1=\begin{bmatrix}-1&0&1&1\\-1&-1&1&1\\2&0&-1&1\\-1&-1&3&-1\end{bmatrix}$
依照上述方法，继续计算 $\pmb{A}_2,\pmb{A}_3$ ，最终得到：
$\begin{split} &\pmb{A}_3=\begin{bmatrix}0&1&9&3\\11&0&8&2\\3&4&0&6\\9&10&6&0\end{bmatrix} \\&\pmb{path}_3=\begin{bmatrix}-1&0&3&1\\2&-1&3&1\\2&0&-1&1\\2&0&3&-1\end{bmatrix} \end{split}$
由 $\pmb{A}_3[i,j]$ 可以得出每一对顶点之间的最短距离，由 $\pmb{path}_3[i,j]$ 能找出对应着该对顶点之间的路径。

例如： $\pmb{A}_3[1,2]=8$ ，即顶点 1 到顶点 2 的最短路径长度是 8。对应的路径： $\pmb{path}_3[1,2]=3$ ，即顶点 2 的前驱是顶点 3，即路径 $< 3, 2 >$ 。由于是从顶点 1 出发，顶点 3 是中间点。而从 $1\to3$ 的路径： $\pmb{path}_3[1,3]=1$ ，即顶点 3 的前驱是 1。故从 $1\to2$ 的路径是 $< 1, 3, 2 >$ ，这条路径最短，长度是 8。

相关文章：