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

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

Fastest way to find all-pair shortest paths in a undirected cycle