Dijkstra heap
Moderator: Board moderators
Dijkstra heap
Can you show me how to use Dijkstra heap?
I don't know what exactly you want to know, but you have to implement
the following functions:
- heapify(v)
- extract-min
- decrease-key(v)
At first,
for all v d[v]=infinity
d[0]=0, where 0 is the starting point
Extract-min returns the vertice with smallest d,
throws it out of the heap, and uses heapify to
keep the condition of the heap. Decrease-key
is useful when you relax an edge and want to decrease
value d of a vertice (when you find a shorter path to it).
You can find those functions on the internet or in
"Introduction to Algorithms"
the following functions:
- heapify(v)
- extract-min
- decrease-key(v)
At first,
for all v d[v]=infinity
d[0]=0, where 0 is the starting point
Extract-min returns the vertice with smallest d,
throws it out of the heap, and uses heapify to
keep the condition of the heap. Decrease-key
is useful when you relax an edge and want to decrease
value d of a vertice (when you find a shorter path to it).
You can find those functions on the internet or in
"Introduction to Algorithms"
