图最短路径无限循环
问题描述:
所以我的油漆技能不是最好的,但我认为它显示了很好的例子。想象一下,我想计算A和C之间的最短路径,考虑到我发现的所有算法都是贪婪的,难道它会陷入A和B之间的无限循环?
任何消耗?
在此先感谢
答
不,不应该有一个无限循环。
图中的访问节点和未访问节点将保持跟踪状态,并且访问节点将永远不会再次访问。
在您的例子:
- 标记所有节点为未访问,除了这是访问
- 与一开始的起始节点,请访问B,作为访问标记B
- B只能访问或作为访问C,但A已经被标记
- 唯一可用的节点是C,这是未访问过
答
我通常把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。
如果您尝试获取所有最短路径的列表,请确保您将每个节点的进程重复为起始节点。 – jdweng
@rob噢,确实很有道理!谢谢。所以我可以在这里使用Dijkstra,对吧? –
是的,你可以在这里使用Dijkstra算法。 – rob