Dijkstra算法与优先队列

Question

5

在我的Dijkstra算法实现中，我有一个包含所有节点的数组和一个包含所有节点的优先队列。每当一个节点被出队时，我会更新所有相邻节点的新距离和它们来自哪里，以便我可以回溯路径。

优先队列中的节点会被更新为新的距离，而数组中的节点会被更新为它来自哪里和新的距离。当一个节点被出队时，数组中的最终距离会被更新：

  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 ++。

- Carlj901

2个回答

0

你可以使用的数据结构：

也许还有其他的可以在数组中找到最小值的方法。

当你更新节点的优先级时，你必须同时同步你选择的数据结构。

注意：如果你使用矩阵来检查连接的节点，你可能不需要使用数据结构，因为它不会改变算法复杂度，仍然是O(N^2)（使用直接循环来查找具有适当优先级的节点）。当图具有大量节点但连接较少且存储为连接节点列表（离散图）时，数据结构才有效。

- Толя

你必须在堆内存中存储节点链接，并在节点在堆内“移动”时同步这些链接。 - Толя

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comingstorm · Accepted Answer

你这里有两种距离：你的优先队列有“临时距离”，可以更新；而你的数组有“最终距离”，不可更新（因为 Dijkstra 算法不需要更新已从优先队列中删除的节点）。

看起来你在不必要地更新数组中的距离。也许把数组节点中的字段名称改为 arrayNode.finalDistance 会是个好主意，以便说明这一点。

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

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

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