Dijkstra's Shortest Path Algorithm | Graph Theory

Explanation of Dijkstra's shortest path algorithm

Dijkstra source code on Algorithms repository:

Video slides:

Indexed Priority Queue Video:

0:00 Intro
0:28 What is Dijkstra's algorithm?
1:13 Algorithm prerequisites
1:55 Video outline
2:28 Dijkstra's algorithm overview
3:50 Lazy Dijkstra's animation
8:10 Lazy Dijkstra's code
11:33 Ignoring stale node optimization
12:11 Finding the shortest path
14:01 Stopping early optimization
15:11 Eager Dijkstra's with an indexed priority queue
16:27 Eager Dijkstra's animation
19:28 Eager Dijkstra's code
20:31 D-ary heap optimization
23:06 The current state of the art for heaps

===================================

[dhrubajyotipaul]

I agree with most people here. This is easily one of the best Dijkstra's Shortest Path Algorithm videos on the internet, if not the best one. I'm so glad that I found you. Thank you making this! ♥

[vnnyboy]

Thank you for taking the time to make these videos.. They are tremendously useful. Hoping to see more in the future ....

[RyuZebian]

Your videos were a HUGE help when I was doing a university course on data structures more than a year ago, and now I'm doing Advent of Code as part of my on-the-job-training. The subreddit kept mentioning "Dijkstra's algorithm" as a way to solve one puzzle.

I'd of course heard about it, but hadn't implemented it by myself before. But I immediately though "FISET will surely have covered it as well as he has his other topics..." And sure enough, this video helped me understand both theory and practice.

Thank you!

[lukay]

Thank you so much, I implemented it to Unreal Engine 4, for my RTS game. I used 100% of my brain for 3 days to make my own path finder, it worked but it was totaly slow

[abijithbahuleyan]

This channel is very much UNDERRATED!!

[matveyshishov]

Thanks a lot! I love your videos, probably the most professionally done on YouTube!

[vivekpal]

Most comprehensive video on Dijkstra. Thank you!

[rish.i]

Outstanding series of videos.ur graph playlist is best on net.Thanks for providing these precious resources for free😃😃😍😍.
Hope u ll make series on advanced data structures like fibonacci heaps(for improving djisktra), binomial heap, suffix tree
Once again thanks for ur effort.

[Mnkmnkmnk]

For anyone trying to implement this, you can solve leetcode 743 network-delay-time using this.

[mickeynig]

The whole BFS and Dijkstra thing clicked for me. Thank you very much!

[manguy]

Amazing man. I thought the MIT videos were good, but YOU ARE THE MAN. You're content has helped me greatly for programming interview concept studying. KEEP IT UP and MUCH LOVE.

[mostinho]

Thanks
1:50 constraint is that graph can’t have negative weight edges
It is a greedy algorithm
Maintain an array/map mapping each node to the min distance we found for it so far. Initialized to inf
5:30 edge relaxation, a node is marked visited when we relaxed all its edges and update our best distances found
5:50 how priority queue works (with djikstra we use a priority queue for the nodes to visit vs a regular queue in bfs)

12:50 To actually reconstruct the path, keep another array/map of the previous node for each node when you update the shortest path found for it (the updated shortest path is the node we’re going to take)
Then you will have a map of Node to Node that maps a node to the previous node in the shortest path

13:00 logic for reconstructing the path from the previous array/map that associated a previous node with each of the nodes

Stopped at 13:30

[AurelianoShowsTheWorld]

Thank you for making the video! Much respect!

[jameskennedy]

Came back here for a little refresher. Great videos!

[orangeshoes]

Thank you for the video!
I wish to ask that the graph you chose at 16:30 to run Dijkstra on has a cycle, doesn't it? between the nodes 1 and 2

[mateusnascimento]

Hi, William! Thanks again for the great video. Just wanted to let you know that the link in the description that you said that redirects to the Indexed priority queue video actually redirects to your video on strongly connected components.

[HarshaVardhan]

In the optimization when there is an end node given at 15:08, we could have checked if index == e before visiting the edges from the end node, as it is unnecessary as we already got the shortest distance to the end node. Please verify my observation.

[zrodger]

Not meaning to brag, but: I've stumbled upon an interesting recreational problem, entailing running 700+ dijkstra's algorithms on a graph of over 1mil nodes (whose adjacency matrix occupies 145GB of disk space). This video was of tremendous value to me, and thank you!

[anwarulbashirshuaib]

15:00 Is it possible to break from the loop as soon as we encounter our destination/target vertex without having to process all its neighbors?

[anuranjankumar]

First of all, kudos for such an amazing content!
I was wondering for the optimisation step at 15:08 can we simply check if the index is visited and continue? (marking visited can be done after this step).
Is there any corner case we will miss in this?