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. 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. 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. It appears that you are unnecessarily updating the distances in your array.
#Python priority queue customized comparator update
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). do something like: PriorityQueue queue = new PriorityQueue() Įdit: It is not advisable to change the priorities of elements in the PQ, hence the need to insert Steps instead of Nodes. Instead, insert another entry for the same node into the PriorityQueue, and ignore duplicates when polling the queue, i.e. I am not certain such an implementation would be faster, though.Ī straightforward idea is to remove and then add the changed node. The Wikipedia article on PriorityQueues might be a good starting point for reading about that. Implementing a priority queue that does is quite involved. PriorityQueue does not offer an api to inform it about a changed node, as that would require it to provide efficient node lookup, which its underlying algorithm does not support. In fact, it doesn't sort its elements at all (that's why its iterator can not promise to iterate elements in sorted order).
Doing that would be too expensive (remember the n log n lower bound for comparison sort), while any reasonable priority queue implementation (including PriorityQueue) promises to add/remove nodes in O(log n). As you discovered, a priority queue does not resort all elements whenever an element is added or removed.
0 kommentar(er)
