algorithm - 如何针对无向对称图优化全对最短路径算法？

Question

如何针对无向对称图优化全对最短路径算法？

由于对另一个问题的误解，我遇到了这个问题，我认为这可能会引起某人的兴趣。

All-Pairs Shortest Paths 可能是一个更有趣的问题，但如果您看到那里有显着的优化，请随意提及 Single-Source Shortest Path。

我不是在寻找最短路径算法的比较，除非您特别关注对称图。

Answer 1

为了希望更好地解释事情，我将使用蝴蝶的比喻（假设翅膀是对称的）。

公共顶点：构成对称线的所有顶点（因此是蝴蝶的身体）。

算法：

• 从图中删除位于对称边之一（及其连接边）上的所有顶点

  去掉一只蝴蝶的翅膀。

• 在这个新图上运行任何最短路径算法

• 您现在拥有从/到所有公共顶点到/从所有其他顶点的最短路径（因为该图是无向的，并且所有删除​​的顶点在这个新图中都有一个对称顶点，它与公共顶点具有相同的距离）

  您现在拥有从/到蝴蝶身体到/从任一翅膀上的任何点的最短路径。这是因为蝴蝶身体上某点到翅膀上某点的距离与身体上某点到另一翅膀上同一点的距离相同，反之亦然。其中任何一个的路径。

• 现在，对于每个非公共顶点a，每个其他非公共顶点b和每个公共顶点，记录从到到c的距离（恒定时间操作（只是加法），因为我们已经有了从到到到的距离）。 从到 的对称顶点（或 到 的对称顶点）的最小距离将是所有公共顶点之间的最小距离。acbaccb
abab

  为了确定从一个机翼上的任何点到另一个机翼上的任何点的最短路径，我们检查从第一个点到身体上的每个点以及从身体上的每个点到第二个点的所有路径，并找到最小的这样距离。