Test yourself
Consider the following graph..Vertex A is the source.
In what order are the vertices taken into consideration?
The shortest lengths from A to B, C, D and E respectively after two iterations are:
What does it do ?
Djikstra's algorithm is used to help one find the shortest path from one node to any other node.
For instance in the following graph, despite the length of the edge from node 5 to node 3 being 14, the shortest path between the edges would be of length 11 (going from node 5 to 2 and then 2 to 3)
What's the idea ?
1) Choose the starting vertex A, from which you want to find the distance to every other node
2) In the beginning, initialize the distance from A to every vertex to be infinity, except A itself, whose distance will be assumed to be 0.
3) Now, consider all the vertices adjacent to A. Say vertex X is adjacent to the current vertex. Then,if
update the distance of AX to the newly found, smaller value.
4) You can now strike A out from the list of vertices which are yet to be considered. Now choose a vertex B, such that its distance from the original source vertex A is the least among all the vertices yet to be considered.
5) Repeat steps 3 to 5 with the new vertex under consideration B instead of A. Keep doing so for all vertices until they are all striked out from the list of vertices to be considered.