data-structures - 哪种算法最适合遍历加权有向图，提供起点和终点？

Question

嗨，我正在寻找最佳算法来找出遍历有向图和加权图的最佳路径。

[大家好，我正在编辑问题以完全解释我的要求]

例如:如果在 5 个节点的图中(让我们分别为所有 5 个节点分配编号 1,2,3,4,5)，如果我希望从节点 2 开始遍历并在 4 结束，覆盖所有节点，那么哪个是解决问题的最佳算法？

我们可以有两个假设:

a) 任意两个节点之间总有一条边。 (意味着对于两个节点(A 和 B)，从 A 到 B 和从 B 到 A 也有一条边。

b) 我们可以遍历一个节点两次(如果需要遍历完整图)。

Answer 1

这是计算机科学中的经典问题，具有众所周知的解决方案。

图是否只有非负边权重？然后使用 Dijkstra’s algorithm或 A* .否则使用 Bellman–Ford algorithm .如果要查找所有节点之间的所有最短路径对，请使用 algorithm of Floyd & Warshall .