我想知道是否有一种算法能够找到从起始节点到终止节点的最短节点序列。图表从起始节点分支出来，具有任意复杂性，并在终止节点处汇聚。所有节点之间的连接都没有权重。
我正在考虑采取从头部和尾部节点开始的探索步骤，直到两端的节点接触等，但我想知道是否存在“更好的方法”，以免重复发明轮子。
我正在考虑采取从头部和尾部节点开始的探索步骤，直到两端的节点接触等，但我想知道是否存在“更好的方法”，以免重复发明轮子。
3个回答
3
使用广度优先搜索，时间复杂度为O(E+V)。这是在无权图上运行最快的算法。
- moinudin
6
谢谢。我考虑的方法是双向广度优先搜索，即从图的两端开始搜索。为了澄清，我不关心图中的所有路径，只关心通过最少节点的路径。 - Olumide
@Olumide 从起点开始进行BFS，当到达终点时停止。这将得到最少的节点数。无需从两端分支。 - moinudin
请查看以下网址获取Java代码：https://dev59.com/zHI-5IYBdhLWcg3w-92b - moinudin
我可能错了，但是我认为从两端进行跟踪可以防止搜索变得像图一样广泛 - 对于非常广泛的图形来说。 - Olumide
只要您不重新访问节点（标记已访问的节点，如链接问题中所示），那么您就可以保证最多处理每个节点一次，这非常快。从每个端点分支可能在某些情况下使其稍微更快，但除非您的图具有非常特定的特征，否则平均而言不会有太大帮助。您始终可以实现两者并比较运行时间。 - moinudin
2不正确 - 从一端开始需要访问所有距离终节点距离<=的节点。从两端开始只需要访问距离任一端点距离<=一半距离的节点。例如，在欧几里得图中，这是节点数量的一半。 - Nick Johnson
1
这是计算机科学中一个非常经典的问题。根据您对图形的描述，您应该首先查看Dijkstra算法
- Rick Sladkey
2
3Dijkstra算法的时间复杂度为O(E+VlogV)，实现起来比BFS更加复杂，而BFS适用于无权图。 - moinudin
在一般情况下，您是正确的。对于无权图的情况，Dijkstra算法中的优先队列可以替换为普通队列，然后该算法就像广度优先搜索一样有效。我没有清楚地说明这种优化。 - Rick Sladkey
0
BFS是解决这些问题的最佳方法，即使您想找到单个节点的最短路径，也必须遍历整个图形以查找是否存在其他可能的路径，而不仅仅是已获得的最短路径。
您还可以绘制BFS树，它将告诉您源节点和任何（也是单个）节点之间的确切最短路线。
- iambruv
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接