在我的 Dijkstra 算法的实现中，我有 1 个包含所有节点的数组和 1 个包含所有节点的优先级队列。每当一个节点出队时，我都会用新的距离和它的来源更新所有相邻节点，这样我就可以回溯路径。
优先级队列中的节点将更新为新距离，数组中的节点将更新其来源位置和新距离。当节点出队时，数组中的最终距离会更新：
PathInfo current = pq.remove();
path[current.pos].distance = current.distance;
使用有关前一个节点的信息更新数组和使用距离的优先级队列是否可以接受？
每当找到更好的距离时就会发生这种情况：
PathInfo key(i, newDistance);
path[i].distance = newDistance;
path[i].previous = current.pos;
pq.decreaseKey(key);
使用基本相同的信息更新我的数组和优先级队列似乎有点多余。
我目前在 PQ 中使用常规数组作为数据结构。更新优先级是在线性时间内完成的，出队也是在线性时间内完成的。
我应该在优先级队列中使用什么数据结构以及如何更改节点优先级？
我正在使用 C++
这里有两种距离：优先级队列具有需要更新的“暂定距离”，而数组具有不会更新的“最终距离”（因为 Dijkstra 算法不需要更新已从优先级队列）。
看来您不必要地更新了数组中的距离。也许更改数组节点中的字段名称来记录这一点也是一个好主意：arrayNode.distance to arrayNode.finalDistance.
换句话说：您似乎正在使用数组节点来输出 Dijkstra 算法的结果 - 因此，当每个数组节点从优先级队列中删除时，您应该只在每个数组节点中设置距离一次。
如果您的优先级队列实现不提供查询与给定键关联的当前距离的功能，请检查其行为decreaseKey()手术。如果decreaseKey()操作拒绝新优先级实际上并未降低的更新，那么您不需要自己执行该检查 - 您只需为当前节点的每个邻居调用它即可。
然而，如果decreaseKey()函数无法正确处理这种情况，并且没有辅助查询函数可以让您手动执行该检查，并且没有机会修复任何一个缺陷，那么您需要为此目的维护冗余信息......
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
