Dijkstra算法与优先级队列 [英] Dijkstra's algorithm with priority queue
问题描述
在我的实现Dijkstra算法我有1阵列的所有节点，并与所有节点1优先级队列。每当一个节点出列我更新与新的距离，它是从哪里来的所有相邻节点，这样我就可以原路返回的路径。
在优先级队列的节点与新的距离更新，并且阵列中的节点被更新它来自何方，并与新的距离。当一个节点被出列阵列中的最终距离被更新：
PATHINFO电流= pq.remove（）;
路径[current.pos] .distance = current.distance;
是可以接受更新两个约previous节点信息，并随着距离的优先级队列的阵列？
这会发生，每当一个更好的距离发现：
PATHINFO键（我，newDistance）;
路径[I] .distance = newDistance;
路径[I] previous = current.pos。
pq.decreaseKey（键）;
这似乎有点多余用基本相同的信息更新我的阵列和优先级队列。
我目前使用的规则阵列作为PQ的数据结构。更新的优先工作是在直线的时间和出队的线性时间也做了。
我应该优先级队列中使用什么数据结构，我应该如何改变一个节点的优先级？
我用C ++
您有两种这里距离：你的优先级队列中有暂行距离这是受更新，而你的数组有最后的距离，这是不（因为Dijkstra算法并不需要更新已经从优先级队列中删除节点）。
看来，你是不必要的更新您的阵列中的距离。也许这也将是一个好主意，改变字段名称阵列节点记录本：从 arrayNode.distance 到 arrayNode.finalDistance 。
在换句话说：它使用的是阵列节点输出从Dijkstra算法的结果出现 - 所以你应该只设置在每个阵列节点的距离一次，当它从优先级队列中删除。
如果您的优先级队列实现不提供查询与给定键关联的当前距离的能力，请检查其 decreaseKey（）操作的行为。如果 decreaseKey（）操作拒绝更新了新的优先实际上并没有减少，那么你不应该需要执行检查自己 - 你可以叫它为当前节点的每个邻居
但是，如果 decreaseKey（）函数没有正确处理这种情况下，并没有辅助查询功能，将让你手动执行检查，并有没有机会来解决任何缺陷，那么你就需要维护冗余信息用于此目的......
In my implementation of Dijkstra's algorithm I have 1 array with all nodes and 1 priority queue with all nodes. Whenever a node is dequeued I update all adjacent nodes with new distance and where it came from, so I can backtrack the path.
The node in the priority queue is updated with new distance and the node in the array is updated where it came from and with new distance. When a node is dequeued the final distance in the array is updated:
PathInfo current = pq.remove();
path[current.pos].distance = current.distance;
Is it acceptable to update both the array with info about previous node and the priority queue with distance?
This happens whenever a better distance is found:
PathInfo key(i, newDistance);
path[i].distance = newDistance;
path[i].previous = current.pos;
pq.decreaseKey(key);
It seems a bit redundant to update my array and priority queue with basically the same info.
I'm currently using a regular array as a data structure in the PQ. Updating the priority is done in linear time and dequeueing is also done in linear time.
What data structure should I use in the priority queue and how should I change a nodes priority?
I'm using C++
You have two kinds of distances here: your priority queue has "tentative distances" which are subject to update, while your array has "final distances", which are not (because Dijkstra's algorithm doesn't need to update nodes that have been removed from the priority queue).
It appears that you are unnecessarily updating the distances in your array. Perhaps it would also be a good idea to change the field name in your array node to document this: from arrayNode.distance to arrayNode.finalDistance.
In other words: it appears you are using your array nodes to output the results from your Dijkstra's algorithm -- so you should only set the distance in each array node once, when it is removed from the priority queue.
If your priority-queue implementation doesn't provide the ability to query the current distance associated with a given key, please check the behavior of its decreaseKey() operation. If the decreaseKey() operation rejects updates for which the new priority does not actually decrease, then you shouldn't need to perform that check yourself -- you can just call it for each neighbor of the current node.
However, if the decreaseKey() function does not handle that case correctly, and there is no auxiliary query function that would let you perform that check manually, and there is no opportunity to fix either deficiency, then you'll need to maintain redundant information for that purpose....
这篇关于Dijkstra算法与优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
