Dijkstra算法回溯路径时出现无限循环问题求助

你的回溯无限循环问题，核心是前驱节点映射（nodePD）中出现了环，或者起始节点的前驱被错误修改，导致从target回溯时永远到不了null（起始节点的前驱本该是null）。下面逐个分析代码里的问题：

1. 条件语句缺失大括号，导致前驱被无差别覆盖 #

看这段代码：

if (getNodeValue == null || (nodeValue.get(currentNode) + nextNodes.get(i).getWeight() < nodeValue.get(getNode)))
    nodeValue.put(getNode, (nodeValue.get(currentNode) + nextNodes.get(i).getWeight()));
    nodePD.put(getNode, currentNode);           

第二个if没有加大括号，导致不管条件是否成立（即不管当前路径是不是更短），nodePD.put(getNode, currentNode);都会执行。这会：

• 强制覆盖节点已有的更优路径前驱，打乱前驱链的正确性；
• 如果后续节点处理时反向设置前驱，会形成环，触发回溯时的无限循环。

2. 多余的前驱初始化逻辑，篡改了起始节点的前驱 #

代码末尾的这段逻辑：

if (nodePD.get(getNode) == null) {
    nodePD.put(getNode, currentNode);
}

它会遍历所有邻接节点，只要节点前驱为null（包括起始节点start），就把前驱设为当前节点。如果图中有边指向start，处理这些边的起点时，start的前驱会被强制修改为该起点，导致：

• 回溯时从target到start后，会继续回溯到start的前驱节点，最终形成环，永远无法终止循环。

3. 未访问边的收集逻辑错误，可能导致重复处理已访问节点 #

unvisitedEdges.add(nextNodes.get(i));写在第一个if (!(visited.contains(getNode)))的外面，会把指向已访问节点的边也加入候选边。后续选择下一个currentNode时，可能选中已访问节点，导致重复处理，进一步打乱前驱链。

修复建议 #

1. 给第二个if加上大括号，确保只有找到更短路径时才更新值和前驱：

if (getNodeValue == null || (nodeValue.get(currentNode) + nextNodes.get(i).getWeight() < nodeValue.get(getNode))) {
    nodeValue.put(getNode, nodeValue.get(currentNode) + nextNodes.get(i).getWeight());
    nodePD.put(getNode, currentNode);           
}

2. 删除多余的if (nodePD.get(getNode) == null)逻辑，Dijkstra算法中前驱只在找到更优路径时更新，无需额外初始化。
3. 把unvisitedEdges.add(nextNodes.get(i));放到第一个if内部，确保只收集指向未访问节点的边：

if (!(visited.contains(getNode))){
    // 原有逻辑
    unvisitedEdges.add(nextNodes.get(i));
}

4. 设置currentNode前判断nextNode是否为null，避免空指针：

if (nextNode != null) {
    currentNode = nextNode.getToNode();
} else {
    break;
}

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