带优先级队列的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

您可以使用的数据结构：

• 敏堆
• 段树
• 芬威克树

也许其他一些在数组中找到最小值。

将优先级更新为节点时，还必须同步预输入的数据结构。

注意:如果您使用矩阵来检查连接的节点，您可以简单地不使用数据结构，因为它不会改变算法复杂性，我仍将是O(N^2)(使用直接循环来查找具有适当优先级的节点)当您的图形具有大量节点和少量连接并存储为连接节点列表(排出的图形)时，数据结构有效

Answer 2

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

您似乎不必要地更新了阵列中的距离。也许更改数组节点中的字段名来记录这一点也是个好主意:从< code>arrayNode.distance更改为< code > array node . final distance 。

换句话说:看起来你正在使用你的数组节点来输出来自你的Dijkstra算法的结果——所以你应该只在每个数组节点中设置一次距离，当它被从优先级队列中删除时。

如果您的优先级队列实现不提供查询与给定键关联的当前距离的功能，请检查其 reduceKey（） 操作的行为。如果 reduceKey（） 操作拒绝了新优先级实际上并未降低的更新，则不需要自己执行该检查 - 您可以只为当前节点的每个邻居html" target="_blank">调用它。

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