Dijkstra's algorithm requires us, in each round, to
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.
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