Dijkstra’s algorithm

why in Dijkstra’s algorithm do we need to use a min heap. when we will visit all of the vertices anyway… why do we need to pop off the smallest vertex from the heap and check it? Why cant we just pop off the first one. at 0 index? Arent all the vertices in the heap the minimum distances? So why would we need to find the minimum of those? We will check them all anyway.

When I run it without heappop and just using pop(0) it still works the same.

Also what does it mean when run time depends on vertices and edges?


This set of lectures talks a lot about different algorithms and shows some of their characteristics if you’re interested (including runtime considerations):

Ok thanks ill take a look, but you dont have a specific answer to my question? As to why we use min heaps instead of lists in Dijkstra’s algorithm?

There’s not a quick answer :slight_smile:

Here’s a more specific discussion on min-heap in dijkstra’s: https://stackoverflow.com/questions/41965431/dijkstra-algorithm-min-heap-as-a-min-priority-queue

But anyways at the core is graph theory and analysis.
And in the lectures it does point out the evolution and contextual basis for why one algorithm might use one technique over another (and the pros and cons). For me, it’s not so much a matter of why, but how it differs from similar algorithms (like A*). Regardless, without the graph theory there is no basis for any of it.

1 Like