Implementing Dijkstra's Algorithm with a Priority Queue

Explanation of how Dijkstra's algorithm can be implemented using a priority queue for greater efficiency. This is also the same as uniform cost search.

[vipulbhardwaj]

really nice visual representation of Dijkstra's, thanks a lot this really helped me with my assignment. :)

[kevinliu]

Best Priority Queue tutorial video ever!!! Thanks Marry

[MrJave_]

Best video on this topic I've found so far. Thank you, professor 👍

[ioannispallis]

Thank you very much professor. With such professors you can be only good student.

[Lod]

Thanks from ETH Switzerland! The visualization is brilliant.

[ApoorvaRajBhadani]

Thanks for this great explanation! Greetings from India!

[ashraf]

great explanation, really helped for my final exam, greeting from malaysia

[frzhouu]

Thanks from China, great explanation!

[pseudolimao]

This is it. If you don't understand dijkstra's with heaps, this demystifies it. I just looked at the code implementation and couldn't comprehend it, but this decomposition helped tremendously.

The key takeaway is how the priority queue pushes down costly jumps to a node X, so when we get to that item in the queue, that node X will already be "marked" by a shorter path, meaning we can discard that item from the queue, essentially skipping steps.
Moreover, since we push "up" the uncostly jumps, our "marks" essentially give us the shortest path to each node, meaning we can stop the algorithm as soon as we have marks equal to the number of nodes.
If you imagine a big graph, you're going to "push down" into the queue a bunch of costly items, you're going to "mark" the nodes rather quickly, finding the shortest path as soon as you mark them all, and discarding a considerable amount of items in the process.

Notice too, that if you have a huge number of edges, compared to vertices, you're doing a lot of work sorting edges in the queue, that you could spend doing lookups, so intuitively you can start being suspicious that this solution might be equal or worse than the naive approach.

I am really pleased with what i unlocked watching this video, thank you Mary. You've also shown me i should, ideally, grab a pen and paper and just go through problems to understand them.

[SEYMABEYAZTAS-ibbz]

Is there an animated code of the dijkstra run in java? if they throw

[harishwarreddy]

If possible try to explain these algorithms along with its pseudo-code.

[Tzyt]

Thanks a lot for this tutorial. Helped me a lot !

[anupritakasbekar]

what is the time complexity and space complexity for this

[sharmanalin]

Great walkthrough! I just want to confirm
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
This condition is already addressed by PQ and should not be used to update distance array every-time we visit neighbours of selected vertex

[xX_dash_Xx]

why did we not include E in the graph, it's gonna feel excluded 😅

[superneutral]

thankyou very much. was very explained