带正权环的有向图：无访问追踪的普通队列版Dijkstra是否会无限循环？

结论：会陷入无限循环，原因如下：

• 原Dijkstra算法的核心逻辑依赖优先队列每次选取当前距离起点最短的节点，且标记已访问后不再处理——因为图中全是正权边，节点第一次被取出处理时，对应的就是到起点的最短路径，后续再遇到该节点的路径只会更长，无需重复处理。
• 改用普通队列+不追踪已访问的方式后，算法失去了“终止重复节点处理”的约束：
  1. 普通队列是先进先出，不按路径长度优先级处理节点；
  2. 每次处理节点时，会把所有子节点（包括已经被处理过的节点）无条件加入队列。
• 当图中存在正权环时，比如存在A→B→C→A的环（每条边权值为正）：
  • 第一次处理A时，会把B加入队列；处理B时把C加入队列；处理C时又会把A加入队列；
  • 后续A被取出处理时，又会重复把B加入队列，以此类推，环内的节点会被无限次加入队列，队列永远无法被清空，算法也就陷入了无限循环。

哪怕后续路径的总长度比已知路径更长，但因为没有“跳过已访问节点”或“仅当路径更短时才更新并加入队列”的判断，只要环存在，节点就会被反复入队，导致循环永不停止。

内容的提问来源于stack exchange，提问作者curiousengineer