Dijkstra's algorithm requires us, in each round, to

- Pick a vertex with minimum burning time
- Change the expected burning time for each neighbour

If we use an adjacency list representation, step 2 will be efficient (note that in this adjacency list we need to store the edge weight as well).

How do we do step 1 efficiently? Suppose we keep the list sorted.

- If the list is an array
- Search is fast (log n)
- Insert is slow (n)
- If the list is a linked list
- Search is slow (n)
- Insert is fast (constant time), once we know where to insert!

Instead, we can use a different data structure, called
a *heap*.

Video lecture on *Heaps*,
NPTEL online course on
Design and Analysis of Algorithms
(Lecture slides)

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky