是否有更好的算法来查找图中的最短路径？

Question

我面临一个必须从图中的两个节点中找到最短路径的问题。该图具有某些特性，我确信可以找到更好的解决方案，因为我发现并想到的所有特性均<。特别是：-该图是单个连接的组件。-该图未定向且未加权。-排列简单周期的节点是一个完整的子图（***）。

给定图的两个节点，我需要找到并返回最小距离。

我研究了加权图和非加权图的不同算法：Dijkstra，Bellman-Ford，Floyd-Warshall和广度优先搜索，但是我找不到使用（***）属性的算法，我非常确定这是重要且有用的。

提前感谢。

Answer 1

如果问题的输入是一个图形和一对顶点，那么仅由于您至少需要读取输入数据，您就无法希望比O（V + E）更快的解决方案。但是，如果您有多个查询（例如K个），则确实可以比O（K *（V + E））做得更好。

如果是这种情况，那么我看到的合并属性（***）的一种方法如下：

如果图是一棵（有根的）树，那么两个顶点之间的最短距离（u，v）是一条路径（u--w--v），其中w是
1. 最小公祖（LCA）存在一种算法，该算法需要一定的预计算时间O（V + E），然后才需要进行实际LCA查询的O（1）时间（例如，描述为here。顶点w，则计算路径的长度非常简单，因为它本质上是（depth（w）-depth（u））+（depth（w）-depth（v）），其中depth（x）是根树中顶点x的深度。
2. 在您的情况下，图形不是树，而是有点像。我将对这种情况下可能发生的情况给出一个高层次的想法。

   [Property（***）告诉我们，每个强连接的分量都是一个完整的子图，并且该分量内部的每对顶点之间的距离为1。因此，如果我们将每个强连接的分量收缩为一个顶点，则可以做类似于上一个案例的事情。

   但是，需要注意一些细微之处。例如，当“压缩的”树中的路径通过顶点时，这可能意味着我们需要访问原始图形中的一个或两个顶点，具体取决于我们是否需要在继续遵循合约之前切换顶点树。但这是我们可以为每个收缩的顶点预计算一次的操作，然后可以再次使每个查询在O（1）时间内运行，因此总体上对于K个查询，我们将拥有O（V + E）进行预处理和O （K）进行查询，使我们总共有O（V + E + K）个时间。