我想知道是否有一种算法可以通过从头节点到尾节点的图来找到最短的节点序列。该图从头节点分支出来，任意复杂，收敛于尾节点。节点之间的所有连接都是未加权的。
我正在考虑解决这个问题，从头节点和尾节点开始探索性步骤，直到图形两端的节点接触等，但我想知道在我（重新）发明之前是否存在“更好的轮子” .
问问题
4566 次
3 回答
3
使用广度优先搜索，它在 O(E+V) 中运行。这是您在未加权图表上获得的最快速度。
于 2010-12-25T01:30:27.280 回答
1
这是计算机科学中美丽的“标准”问题之一。鉴于您对图表的描述，您应该首先查看Dijkstra 的算法
于 2010-12-25T01:34:09.610 回答
0
BFS 是解决这类问题的最佳选择，即使您想找出单节点最短路径，您也必须遍历整个图以查找除了已经获得的最短路径之外是否还有其他可能的路径。
您还可以绘制一个 BFS 树，它将准确地告诉您源和任何（也是单个）节点之间的最短路径。
于 2016-06-29T17:06:16.753 回答