Dijkstra的算法具有优先级队列

Question

在我对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++

Answer 1

这里有两种距离：优先级队列具有需要更新的“暂定距离”，而数组具有不会更新的“最终距离”（因为 Dijkstra 算法不需要更新已从优先级队列）。

看来您不必要地更新了数组中的距离。也许更改数组节点中的字段名称以记录这一点也是一个好主意： fromarrayNode.distance到arrayNode.finalDistance。

换句话说：您似乎正在使用数组节点来输出 Dijkstra 算法的结果 - 因此，当每个数组节点从优先级队列中删除时，您应该只在每个数组节点中设置距离一次。

如果您的优先级队列实现不提供查询与给定键关联的当前距离的功能，请检查其decreaseKey()操作的行为。如果decreaseKey()操作拒绝新优先级实际上并未降低的更新，那么您不需要自己执行该检查 - 您只需为当前节点的每个邻居调用它即可。

但是，如果该decreaseKey()函数不能正确处理这种情况，并且没有辅助查询函数可以让您手动执行该检查，并且没有机会修复任一缺陷，那么您将需要为此目的维护冗余信息....