算法技术手册（原书第2 版）

154

｜

第

6

章

6.7.2 解决方案

动态规划方法将会依序计算更小的子问题。考虑

G

的边：它们代表了两个顶点

u

和

v

之

间最短路径的长度，这条路径

不包含任何其他顶点

。因此，

dist[u][v]

矩阵首先被初始

化为

∞

，

dist[u][u]

被设置为

0

（确认从顶点

u

到其自身的路径没有任何费用）。最后，

dist[u][v]

被设置为每条边

(

u

,

v

)

∈

E

的权值。在这个点上，

dist

矩阵包含了当前计算

出的点对

(

u

,

v

)

之间的最优最短路径。

接着考虑稍大一点的子问题，即计算任意点对

u

和

v

之间的最短路径，但是这条路径

也

许会包含顶点

v

1

。动态规划会检查每个顶点对

(

u

,

v

)

，检查是否存在路径

{

u

，

v

1

，

v

}

拥

有比当前数字更小的总距离。在某些情况下，

dist[u][v]

会依然是

∞

，因为在

u

和

v

之

间还没有任何信息。而在其他时候，从

u

到

v

1

，再从

v

1

到

v

的路径和要比当前距离更好，

这时算法会在

dist[u][v]

中

记录新的总长度。接下去，再大一点的子问题是尝试解决

任意两个点对

u

和

v

之间的最短距离，但是

可能会包含

顶点

v

1

或者

v

2

。最终，算法会将

这些子问题不断扩展，直到

dist[u][v]

矩阵中的结果包含任意两个顶点

u

和

v

之间的

最短路径，而这条路径也许会包含图中的任意顶点。

Floyd-Warshall

算法

计算的关键优化是判断

dist[u][k] + dist[k][v]

是否小于

dist[u][v]

。

注意，算法同样计算了

pred[u][v]

矩阵，它用于“记住”新的从

u

到

v

的最短路径必须经过顶点

k

。例

6-6