The algorithm was developed by a Dutch computer scientist Edsger W. Dijkstra in 1956. It is used to find the shortest path between a node/vertex (source node) to any (or every) other nodes/vertices (destination nodes) in a graph. A graph is basically an interconnection of nodes connected by edges. This algorithm is sometimes referred to as Single Source Shortest Path Algorithm due to its nature of implementation.
Table of content
Before diving into any algorithm, its very much necessary for us to understand what are the real world applications of it. Majority of the problems that we encounter in real life scenarios deals with finding solutions to shortest path based problems. To explain in simple words, you want to travel from city A to city B. Both cities are connected by multiple routes. What route do we generally prefer? There is no doubt that we would opt for the route which can make us reach our destination with minimum possible cost and time! Isn’t this relatable?
Following are the main applications of Dijkstra’s Algorithm:
In order to find the shortest path, Dijkstra’s algorithm mainly allocates a “cost” value taken to reach the destination vertex from the source vertex. The “cost” can be mapped to disance, money or time taken to reach from source to a destination.
Below are the steps to be followed for solving using Dijkstra’s algorithm:
Minimum( existing cost of V2 , (sum of cost of V1 + the cost of edge from V1 to V2) )
Consider the map below. The cities have been selected and marked from alphabets A to F and every edge has a cost associated with it.
We need to travel from Bengaluru to all other places and we have to identify what are the shortest paths with minimal cost from Bengaluru to other destinations.
Upon conversion, we get the below representation. Note that the graph is weighted and undirected. All the cities have been replaced by the alphabets associated with it and the edges have the cost value (to go from one node to other) displayed on it.
Assign cost of 0 to source vertex and ∞∞ (Infinity) to all other vertices as shown in the image below.
Maintain a list of unvisited vertices. Add all the vertices to the unvisted
list.
For each neighbor A, C and D of source vertex selected (B), calculate the cost associated to reach them from B using the formula. Once this is done, mark the source vertex as visited (The vertex has been changed to blue to indicate visited).
Minimum(current cost of neighbor vertex, cost(B)+edge_value(neighbor,B))
Choose the unvisited vertex with minimum cost (here, it would be C) and consider all its unvisited neighbors (A,E and D) and calculate the minimum cost for them.
Once this is done, mark C as visited.
Minimum(current cost of neighbor vertex, cost(C)+edge_value(neighbor,C))
Observe that the cost value of node D is updated by the new minimum cost calculated.
Repeat step 4 until there are no unvisited nodes left. At the end of the execution, we will know the shortest paths from the source vertex B to all the other vertices. The final state of the graph would be like below.
Dijkstra_Algorithm(source, G):
"""
parameters: source node--> source, graph--> G
return: List of cost from source to all other nodes--> cost
"""
unvisited_list = [] // List of unvisited verticesvertices
cost = []
cost[source] = 0 // Distance (cost) from source to source will be 0
for each vertex v in G: // Assign cost as INFINITY to all vertices
if v ≠ source
cost[v] = INFINITY
add v to unvisited_list // All nodes pushed to unvisited_list initially
while unvisited_list is not empty: // Main loop
v = vertex in unvisited_list with min cost[v] // v is the source node for first iteration
remove v from unvisited_list // Marking node as visited
for each neighbor u of v: // Assign shorter path cost to neigbour u
cost_value = Min( cost[u], cost[v] + edge_cost(v, u)]
cost[u] = cost_value // Update cost of vertex u
return cost
Consider there are V number of vertices in a graph. Then by definition, there would be |V-1| number of edges.
Hence the total running time will have an upper bound of O(|V| * |V-1|) which is equivalent to O(|V|^{2})
O((E+V)*LogV) = O(ELogV)
where E is the number of edges and V is the number of vertices in a graphHow can we be sure that Dijkstra’s algorithm provides us the shortest possible path between two nodes? Let’s go through the following explanation to understand whether this algorithm always gives us the shortest possible path.
Consider the following notations:
D(s,u) = the minimum distance as calculated by Dijkstra's algorithm between nodes s and u
d(s,u) = the actual minimum distance between nodes s and u
According to Dijkstra’s Algorithm, D(s,u) = d(s,u)
Proof:
Let us start by assuming that Dijkstra’s Algorithm is incorrect.
u
is included into the Visited List which indicates => D(s,u) > d(s,u)
Let x
be the first of these vertices that was pushed into the Visited List. Then,
x
is included into the Visited List: D(s,x) > d(s,x)
z
that were included into the Visited List signifies D(s,z) = d(s,z)
x
is included into the Visited List.
P
be the (real) shortest path from s
to x
z
be the first node that is not in the “Visited List” and is along the shortest path.y
be the predecessor node of z
on the shortest path P
D(s,y) = d(s,y)
… (1) (This means the minimum distance s
to y
computed by the algorithm = actual min. distance s
to y
as y
is included before x
)D(s,z) = D(s,y) + edge_cost(y,z) = d(s,y) + edge_cost(y,z)
… (2)D(s,x) ≤ D(s,z)
…(3) (Because the next vertex included by the algorithm is x
)We can now finally deduce that:
D(s,x) ≤ D(s,z) ... From (3)
= d(s,y) + edge_cost(y,z) ... From (2)
≤ d(s,y) + edge_cost(y,z) + d(z,x)
= d(s,x)
The above result contradicts the assumed fact of Dijkstra’s algorithm being incorrect earlier.
Hence, by proof of contradiction, we can say that Dijkstra’s algorithm always gives us the shortest possible path between 2 nodes which is: D(s,x) should be equal to d(s,x)
Log In using