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

2024-05-18 • 问答

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

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

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

谢谢。

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

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

如果图是一棵（有根的）树，则两个顶点之间的最短距离（u，v）是一条路径（u--w--v），其中w是最小公祖先 u和v的（LCA）。存在一种算法，该算法在特定的预计算中花费O（V + E）时间，然后在实际的LCA查询中花费O（1）时间（例如，{{3} }。一旦有了顶点w，就可以直接计算路径的长度，因为它实质上是（depth（w）-depth（u））+（depth（w）-depth（v）），其中depth（x）是我们的根树中顶点x的深度。
在您的情况下，该图不是树，而是有点像。我将对这种情况下可能发生的情况给出一个高层次的想法。

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

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