有没有更好的算法来找到图中的最短路径？
Is there a better algorithm to find the shortest path in a graph?
我遇到了一个问题，我必须从图中的两个节点找到最短路径。该图具有一些特征，我相信这些特征可以带来更好的解决方案，因为到目前为止我发现和想到的所有特征都是 O(V+E)。
特别是：
- 该图是单个连接的组件。
- 该图未定向且未加权。
- 排列一个简单循环的节点是一个完整的子图(***)。
给定图形的两个节点，我需要找到 return 最小距离。
我查看了不同的算法，用于加权和未加权图：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) 时间进行特定的预计算，然后使用 O(1) 时间进行实际的 LCA 查询（例如，描述, here。一旦你有了顶点 w，就可以直接计算路径的长度，因为它本质上是 (depth(w) - depth(u)) + (depth(w) - depth( v)), 其中 depth(x) 是有根树中顶点 x 的深度。
在你的例子中，图形不是一棵树，但有点像一棵树。我将对这种情况下可能发生的事情给出一个高层次的想法。
属性 (***) 告诉我们每个强连通分量都是一个完备子图，并且这样的分量内部的每对顶点之间的距离为1。因此，如果我们收缩每个强连通将组件合并到一个顶点中，然后我们可以做与之前的情况类似的事情。
但是，需要注意一些细微之处。例如，当 "contracted" 树中的一条路径经过一个顶点时，这可能意味着我们需要访问原始图中的一个或两个顶点，这取决于我们是否需要在继续之前切换顶点我们承包的树。但这是我们可以为每个收缩顶点预先计算一次的东西，然后可以在 O(1) 时间内再次对 运行 进行每个查询，因此总的来说，对于 K 个查询，我们将有 O(V + E)用于预处理和 O(K) 用于查询，给我们总 O(V + E + K) 时间。
我遇到了一个问题，我必须从图中的两个节点找到最短路径。该图具有一些特征，我相信这些特征可以带来更好的解决方案，因为到目前为止我发现和想到的所有特征都是 O(V+E)。
特别是：
- 该图是单个连接的组件。
- 该图未定向且未加权。
- 排列一个简单循环的节点是一个完整的子图(***)。
给定图形的两个节点，我需要找到 return 最小距离。
我查看了不同的算法，用于加权和未加权图：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) 时间进行特定的预计算，然后使用 O(1) 时间进行实际的 LCA 查询（例如，描述, here。一旦你有了顶点 w，就可以直接计算路径的长度，因为它本质上是 (depth(w) - depth(u)) + (depth(w) - depth( v)), 其中 depth(x) 是有根树中顶点 x 的深度。
在你的例子中，图形不是一棵树，但有点像一棵树。我将对这种情况下可能发生的事情给出一个高层次的想法。
属性 (***) 告诉我们每个强连通分量都是一个完备子图，并且这样的分量内部的每对顶点之间的距离为1。因此，如果我们收缩每个强连通将组件合并到一个顶点中，然后我们可以做与之前的情况类似的事情。
但是，需要注意一些细微之处。例如，当 "contracted" 树中的一条路径经过一个顶点时，这可能意味着我们需要访问原始图中的一个或两个顶点，这取决于我们是否需要在继续之前切换顶点我们承包的树。但这是我们可以为每个收缩顶点预先计算一次的东西，然后可以在 O(1) 时间内再次对 运行 进行每个查询，因此总的来说，对于 K 个查询，我们将有 O(V + E)用于预处理和 O(K) 用于查询，给我们总 O(V + E + K) 时间。