给定一个图和目标节点，如何找到所有其他顶点到目标顶点的最短路径。
4个回答
18
迪杰斯特拉算法。你可以从反向的角度去考虑，将目的地作为起点。这样可以给你任何其他节点的距离和路径。
*PS：只有一件事需要记住。在应用迪杰斯特拉算法之前，你需要先翻转边缘，并以你的目的地作为起点才能使其正常工作。
- Nik
1
假设它是双向的，你可以从目的地开始，向外扩展。这通常被称为广度优先搜索（BFS）。
任何与目标相连的东西距离为1。任何连接到这些节点中的任何一个（尚未计算的）的距离为2。重复此过程，直到没有节点为止。
即使它不是双向的，你仍然可以通过对节点进行单次遍历来“伪造”其双向性。
无论如何，这样做的顺序是（V + E），其中V是您的节点数，E是您的边数。
- corsiKa
4
这不太可能给他想要的东西。他想要从任何节点到目标节点的路径。 - Nik
@nik 显然，你是在一路上存储路径。我应该明确地提到这一点。@Davin 这是一个BFS。你可以（轻松地）适应它来考虑权重边，方法是将获取的节点放入优先队列中，并使用贪心算法，比较到达的节点以检查它们到根的距离加上到那里的距离是否小于当前到根的距离。 - corsiKa
答案中应该写BFS，从描述中并不是很清楚。运行时间是线性的，即O（V+E），不确定你答案中的“n”是什么意思。不确定我是否理解了为考虑加权边而进行的“适应”，我不知道有哪些算法可以在线性时间内解决最短路径问题，尤其是BFS！ - davin
@davin 你说得对，虽然适应过程在实现方面很简单，但对运行时间有着极大的影响。感谢你对
O(V+E)的澄清。我已经相应地修改了帖子。 - corsiKa0
Dijkstra算法在带权边且需要最小化路径上的权重总和时效果良好，但在无权图中（所有边的代价相同），简单的广度优先搜索即可完成任务。
- njlarsson
0
为了完善上面最有帮助的答案。
在应用 Dijkstra 算法之前，您需要将图的边反转，并以目标作为起始顶点。
- Shibata
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接