Dijkstra's Algorithm: Shortest Path

Dijkstra's Algorithm is used millions of times a day on Internet mapping sites (such as Google Maps) to find the shortest path between two points.

Dijkstra's algorithm actually finds the lowest cost between one vertex and all other vertices in a weighted graph. But with a simple modification, it can find the shortest path--not just the lowest cost--between two vertices.

Category:

Education

Tags:

• cs
• computerscience
• discretestructures
• algorithms

[profbbrown]

You're all right about the errors in this video. I'll have to post a corrected one!

[maheekz]

Dijkstra should produce the shortest path to all vertices from A in this case. So how come C is having A9 when it can have a shorter path with B6 ? I think it is not correct to go to C after doing A. You need to do B since it has the minimum weight from A. Is this correct?

[masterchief9064]

You have done this incorrectly. From A you should have gone to B first. The algorithm states that you use the smallest path from the 'current node'. From B to C is 6 as opposed to A to C which was 9.

[BangaloreGuy2010]

There might be some errors but the video is very clear and helps explain the concept very well. Thanks

[ShallowHeartNB]

it is correct, you start with a node and see what directions you can go and take the smallest one and keep looking for better paths - watch?v=8Ls1RqHCOPw

[smlzgr12]

yes it is very very helpful but it doesn`t mean they are wrong. that error may confuse someone

[helibbc]

Despite the fact that everybody wants to prove that they are so smart, the video is REALLY helpful. I have a final exam tomorrow and the text book didnt explain this well. YOU SAVED MY ASS

[0rdon]

Thanks for the upload it's very usefull and clear!

[PlunderGames]

Very helpful. I "thought" I understood the algorithm, but when the time came to implement this in a project, I found I did not. This helped the logic of my code flow much better. Thank you!

[008him]

Actually this algorithm works a bit differently. After we are done with A, we should have jumped to B rather than to C in 2nd step and then seen the shortest path. The reason is that in this algo, we are supposed to jump in an order of shortest path from a given node. So after 1st iteration, shortest from A is B and not C. The reason behind this is that there may be a shorter path to C via B, which you can see in this video is there. Still Thank you Profbbrown. This video was of great help.

[hle610]

Why C not be B6, short than A9?