图最短路径无限循环

Question

所以我的油漆技能不是最好的，但我认为它显示了很好的例子。想象一下，我想计算A和C之间的最短路径，考虑到我发现的所有算法都是贪婪的，难道它会陷入A和B之间的无限循环？

任何消耗？

在此先感谢

Answer 1

不，不应该有一个无限循环。

图中的访问节点和未访问节点将保持跟踪状态，并且访问节点将永远不会再次访问。

在您的例子：

1. 标记所有节点为未访问，除了这是访问
2. 与一开始的起始节点，请访问B，作为访问标记B
3. B只能访问或作为访问C，但A已经被标记
4. 唯一可用的节点是C，这是未访问过

Answer 2

我通常把INT o每个节点从起点开始的距离和路径（节点列表）。当我输入一个节点时，我将当前距离与现有距离进行比较。如果当前距离比现有距离短，我用旧路径替换新路径。

另一种方法是保存每个节点到每个其他节点的距离列表。在离开每个节点时填写此列表。

从A开始：设置A已经访问过。转到B.然后回到A. A已经被访问过，所以在B添加到B到A的距离为26. 从B移动到D.然后返回到B. B已经访问过，所以在D添加距离D到B为96 。从D到A的距离为96 + 26 = 112. 从D移动到E.然后返回D. D已经访问过，所以在E加上距离E到D为21.添加从E到B的距离为21 + 96 = 117.将距离E添加到A，作为21 + 96 + 26 = 143。