在无向循环中找到全对最短路径的最快方法

Question

我有一个无向图它本身就是这样一个简单的循环

a---b---c
|       |       
d---e---f

在此条件下，哪一种方法是计算全对最短路径的最快方法?

Answer 1

从A开始顺时针遍历图一次，每个节点计算到A的距离。我们设到节点X的距离是a[X]。这样，对于任意一对(X, Y)的节点，距离将为:

min(abs(aX - aY), total - abs(aY - aX))

其中total为所有边权值之和。

在您的情况下，a[B](我将使用大写的节点)将是1,a[C]将是2,a[D]将是3等，总数将是6。如果你想计算b和f之间的距离，它应该是

min(abs(aB - aF), total - abs(aB - aF)) = 
min(abs( 1 -  3),     6 - abs( 1 -  3)) = 
min(           2,                    4) =
2