5

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

4

2 回答 2

1

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

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

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

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

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

于 2013-02-19T20:56:29.083 回答
0

您可以使用的数据结构：

也许其他一些可以在数组中找到最小的。

当您更新节点的优先级时，您还必须同步您喜欢的数据结构。

注意：如果您使用矩阵来检查连接节点，您可能根本不使用数据结构，因为它不会改变算法复杂度我仍然是 O(N^2)（使用直接循环找到具有适当优先级的节点）图有很多节点和少量连接，并存储为连接节点列表（放电图）

于 2013-02-19T14:36:10.977 回答