图最短路径无限循环
Graph shortest path infinite cycle
所以我的绘画技巧不是最好的，但我认为它很好地展示了这个例子。想象一下，我要计算A和C之间的最短路径，考虑到我找到的所有算法都是贪心的，那岂不是会陷入A和B之间的无限循环？
有什么建议吗？
提前致谢
不，不应该有无限循环。
图表中的已访问和未访问节点会被跟踪，已访问节点将永远不会被再次访问。
在你的例子中：
- 将所有节点标记为未访问，但已访问的起始节点除外
- 从A开始，访问B，将B标记为已访问
- B只能访问A或C，但A已经被标记为已访问
- 唯一可用的节点是C，未访问
我通常将距起点的距离和路径（节点列表）放入每个节点。当我进入一个节点时，我将当前距离与现有距离进行比较。如果当前距离比现有距离短，我用旧路径替换新路径。
另一种方法是保留每个节点到其他每个节点的距离列表。离开每个节点时填写此列表。
Start at 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.
所以我的绘画技巧不是最好的，但我认为它很好地展示了这个例子。想象一下，我要计算A和C之间的最短路径，考虑到我找到的所有算法都是贪心的，那岂不是会陷入A和B之间的无限循环？
有什么建议吗？
提前致谢
不，不应该有无限循环。
图表中的已访问和未访问节点会被跟踪，已访问节点将永远不会被再次访问。
在你的例子中：
- 将所有节点标记为未访问，但已访问的起始节点除外
- 从A开始，访问B，将B标记为已访问
- B只能访问A或C，但A已经被标记为已访问
- 唯一可用的节点是C，未访问
我通常将距起点的距离和路径（节点列表）放入每个节点。当我进入一个节点时，我将当前距离与现有距离进行比较。如果当前距离比现有距离短，我用旧路径替换新路径。
另一种方法是保留每个节点到其他每个节点的距离列表。离开每个节点时填写此列表。
Start at 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.