Implementing Dijkstra's Algorithm with a Priority Queue

[@MrJave_]

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

[@maryelainecaliff]

I'm glad you found it helpful.

[@kevinliu5750]

Best Priority Queue tutorial video ever!!! Thanks Marry

[@maryelainecaliff]

Thanks! I'm glad you found it helpful.

[@ioannispallis7258]

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

[@maryelainecaliff]

I appreciate the compliment.

[@vipulbhardwaj1599]

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

[@maryelainecaliff]

I'm glad it helped.

[@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.

[@maryelainecaliff]

I'm glad you found the video helpful. I think you're right that the key to understanding is with the ideas and diagrams, because we don't get bogged down in the specifics of code. Then once we really understand what's going on, it becomes much easier to translate into code (in any language).

[@pseudolimao]

@@maryelainecaliff the code is just that, code for a set of ideas. and some key ideas, especially for these fundamental algorithms' optimized implementations, are very obfuscated within the code. From the array implementation to the priority queue one, the key takeaway is that sorting the queue by edge weight gives us the optimal edge as the first edge we process between those nodes (if one edge is always smaller than two, aka no negative weights), which is almost impossible to decipher this without brute forcing examples in your head/paper or having someone explain it to you, but it's really beautiful once you actually grasp the intention.

[@ApoorvaRajBhadani]

Thanks for this great explanation! Greetings from India!

[@maryelainecaliff]

You are certainly welcome. I'm glad you found it helpful.

[@Lod531]

Thanks from ETH Switzerland! The visualization is brilliant.

[@maryelainecaliff]

Thank you.

[@frzhouu2676]

Thanks from China, great explanation!

[@maryelainecaliff]

You are welcome!

[@ashraf3576]

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

[@maryelainecaliff]

Terima kasih. Glad it helped.

[@harishwarreddy2916]

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

[@maryelainecaliff]

Thanks for the suggestion. However, you will find high-level pseudocode for the algorithm in the breadth-first-search video. The algorithm is largely the same, with the primary differences being the use of the priority queue and, of course, the use of the weight of each edge in the cost calculation.

[@MissChelsie24]

Best video I've seen on this!

[@maryelainecaliff]

Thank you.

[@SEYMABEYAZTAS-ib4bz]

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

[@59sharmanalin]

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

[@maryelainecaliff]

That's correct. We're moving from keeping track of the best cost seen so far in the cost array to putting that into the priority queue to manage for us.

[@59sharmanalin]

@@maryelainecaliff Great, thanks!! Keep up the good work, below I just implemented the algo, it's very intuitive and easy algo

[@anupritakasbekar8172]

what is the time complexity and space complexity for this

[@maryelainecaliff]

That actually depends on the implementation of your graph representation (adjacency list or adjacency matrix) and the implementation of your priority queue. For a discussion of some of the possibilities, you can check out www.baeldung.com/cs/dijkstra-time-complexity.

[@shaniduplessis9102]

Great explanation, thank you!

[@maryelainecaliff]

Glad it was helpful!

[@Tzyt2345]

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

[@maryelainecaliff]

Glad to hear that!

[@williamson-mcgee7365]

Great tutorial!

[@superneutral1663]

thankyou very much. was very explained

[@maryelainecaliff]

I'm glad you found it helpful.

[@varalakshmimamillapalli9964]

Thank you so much ...❤️❤️❤️♥️

[@ShivamKendre-fc3su]

Thank you so much

[@maryelainecaliff]

Glad you found it helpful.

[@juandiegobermeo5029]

just great, thank you very much!

[@maryelainecaliff]

Glad you liked it!

[@xX_dash_Xx]

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

[@xX_dash_Xx]

AND I

[@xX_dash_Xx]

thank you for saving my ass this semester tho. great vid

[@maryelainecaliff]

:-)

[@illicitlegacy3783]

You are the best!!!

[@jerenannagurbanovastudent1082]

the best explanation

[@maryelainecaliff]

Glad it was helpful!

[@nurtasshyntas7745]

Very good! Thanks

[@maryelainecaliff]

Thank you. I'm glad you found it helpful.

[@sahnawaz]

Amazing!

[@maryelainecaliff]

Thank you.

[@JordanCagle-k9x]

live roger reaction

[@SolidCode]

Great Explanation 😀

[@maryelainecaliff]

Glad it was helpful!