How to Update Heap in Dijkstra Shortest Path Algorithm
Nov 03, 2013When we use a heap to improve the runing time of Dijkstra shortest path algorithm from to , we may find that it is not easy to keep the heap in heap order just using insert() or delete(). This post describes the update of that heap.
I suppose that you might:
- know how to wirte Dijkstra algorithm with running time, and
- know how to use heap.
为了将Dijkstra最短路径算法的时间复杂度从 降低到 ，我们可以使用 heap 。不过迭代中的每一次更新heap的过程，我们需要一些技巧来保持heap的有序性。本文就会指出该技巧，并且解释我在算法代码中的一些变动。
To speed up the finding minimum length of path in each stage in Dijkstra shortest path algorithm, we can use a binary heap to store frontier path, according to many words, like Heap Application, or Tim Roughgarden’s algorithm course.
function dijstra(graph, s) {
s = s || 1;
i = 0;
frontier = new Heap();
frontier.push([s, 0]);
while ( !frontier.isEmpty && i < graph.n ) {
// O(logn) on pop() instead of O(n)
// from linear selection of minimum length
current = frontier.pop();
graph.edgesOf(current)
.filter(v => !v.isVisisted)
.forEach(v =>
if (frontier.has(v))
// update path length on v in frontier
else:
frontier.push([v, current[1] + weightOf(current, v)]);
);
}
}
It sounds easy, however the 1st revision of dijkstra() in Algo.js is failed to update heap correctly, where I just update the value of one vertex without keeping heap order.
if (g.__labelAt__(v[0]) === -1){
// not visited, update each in frontier
var updated = frontier.__id__.some(function(x){
return x && (x[0] === v[0]) &&
(x[1] = Math.min(x[1], current[1] + v[1]), true);
});
if (!updated){
frontier.push([v[0], v[1]]);
}
} // end if, unvisited
How to update and keep heap order?
While, when we update the MinHeap, it means that we may replace the item at that index with a value LESS than the origin one. According to the definition of minimum binary heap, each parent is less than their children. (see picture from Wikipedia)
So, if we replace with a LESS value called .
is still less than its children,
but may be less than (its parent).
As the algorithm of push() of heap, we need to exchange with its parent, great-parent…, until heap is ordered. That is:
Using heap.swim() to update that heap. (see diff of revision)
var updated = frontier.__id__.some(function(x, k){
// return x && x[0] === v[0] && (doUpdate, true)
return x && (x[0] === v[0]) &&
((function(){
if (current[1] + v[1] < x[1]) {
x[1] = current[1] + v[1];
// swim like push() in heap is important to update heap
frontier.__swim__(k);
}
})(), true);
});
heap.swim() 来维持heap的有序性。