Dijkstra's Algorithm

Working of Dijkstra's Algorithm

Highlights:

1. Greedy Algorithm
2. Relaxation

Dijkstra's Algorithm requires a graph and source vertex to work.The algorithm is purely based on greedy approach and thus finds the locally optimal choice(local minima in this case) at each step of the algorithm.

In this algorithm each vertex will have two properties defined for it-

• Visited property:-
  • This property represents whether the vertex has been visited or not.
  • We are using this property so that we don't revisit a vertex.
  • A vertex is marked visited only after the shortest path to it has been found.
• Path property:-
  • This property stores the value of the current minimum path to the vertex. Current minimum path means the shortest way in which we have reached this vertex till now.
  • This property is updated whenever any neighbour of the vertex is visited.
  • The path property is important as it will store the final answer for each vertex.

Initially all the vertices are marked unvisited as we have not visited any of them. Path to all the vertices is set to infinity excluding the source vertex. Path to the source vertex is set to zero(0).

Then we pick the source vertex and mark it visited. After that all the neighbours of the source vertex are accessed and relaxation is performed on each vertex. Relaxation is the process of trying to lower the cost of reaching a vertex using another vertex.

In relaxation, the path of each vertex is updated to the minimum value amongst the current path of the node and the sum of the path to the previous node and the path from the previous node to this node.

Assume that p[v] is the current path value for node v, p[n] is the path value upto the previously visited node n, and w is the weight of the edge between the curent node and previously visited node(edge weight between v and n)

Mathematically, relaxation can be represented as: $p[v]=minimum(p[v] , p[n] + w)$

Then in every subsequent step, an unvisited vertex with the least path value is marked visited and its neighbour's paths are updated.

The above process is repeated till all the vertices in the graph are marked visited.

If any of the vertex is not reachable(disconnected component), its path remains infinity. If the source itself is a disconected component, then the path to all other vertices remains infinity.

Algorithm

1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node, lets say C.
3. For each neighbour N of the current node C: add the current distance of C with the weight of the edge connecting C-N. If it is smaller than the current distance of N, set it as the new current distance of N.
4. Mark the current node C as visited.
5. Go to step 2 if there are any nodes are unvisited.

Dijkstra Algorithm Example

Lets take an example to understand the algortihm better.

Lets assume the below graph as our input with the vertex A being the source.

• Initially all the vertices are marked unvisited.
• The path to A is 0 and for all the other vertices it is set to infinity.
• Now the source vertex A is marked as visited.Then its neighbours are accessed (only accessed and not visited).
• The path to B is updated to 4 using relaxation as the path to A is 0 and path from A to B is 4, so min((0+4),∞) is 4.
• The path to C is updated to 5 using relaxation as the path to A is 0 and path from A to C is 5, so min((0+5),∞) is 5. Both the neighbours of A are relaxed so we move ahead.
• Then the next unvisited vertex with least path is picked and mark it visited. So vertex B is now visited and its unvisited neighbours are relaxed. After relaxing path to C remains 5, path to E becomes 11 and path to D becomes 13.
• Then vertex C is picked and mark it visited and its unvisited neighbour E is relaxed. While relaxing E, we find that the path to E via C is smaller than its current path, so the path to E is updated to 8. All neighbours of C are now relaxed.
• Vertex E is picked and mark it visited and its neighbours D and F are relaxed. Path to D remains 13 and path to F becomes 14(8+6).
• Then vertex D is picked and mark it visited and only F is relaxed. The path to vertex F remains 14.
• Now only vertex F is remaining so it is visited but no relaxations are performed as all of its neighbours are already visited.
• As soon as all the vertices become visited the program stops.

The final paths we get are:

• $A=0(source)$
• $B=4(A->B)$
• $C=5(A->C)$
• $D=13(A->B->D)$
• $E=8(A->C->E)$
• $F=14(A->C->E->F)$

Psuedocode

This the pseudocode for Dijkstra's algorithm.

We get the minimum path to each vertex from the source vertex in the distance array.

Implementations for Dijkstra's Algorithm

1. Implementation of Dijkstra Algorithm in C++

Output for Above Code

Explanation of C++ Code

• This is the explanation for the above C++ code.

• First let's recall what all we require for Dijkstra's Algorithm. We need a graph and a source vertex.

• The graph and source are defined in the main function.

• First function we have is the minDist function. This function returns a vertex which has the smallest path and is also unvisited.

• Next we have is the printSolution function which prints the distance array.

• Then we have the dijkstra function. This is where most of the work is done. An array named distance has been created which stores the distance to each node from the source. Initially, all the values in the array are set to INT_MAX(it used to represent infinity) except the source which is set to zero.

• Then we have another array visited which stores whether a vertex has been visited or not. Initially we mark all the vertices as unvisited (represented here by false).

• Then a loop is run V times. In every iteration the minDist function is called to pick the unvisited node with the smallest path. The picked node is then marked visited.

• Then all the neighbours of the picked node are relaxed. This means that for each neighbour, we try to find a path to it using our currently picked node and if we find such a path that is also smaller than the node's current path, the node's path is updated to this newly found path.(distance[node]] is updated).

• This process is continued for all the nodes of the graph and finally the printSolution function is called to print the solution.

2. Implementation of Dijkstra Algorithm in JAVA

Output for Above Code

3. Implemetation of Dijkstra Algorithm in Python

Output for Above Code

Dijkstra Algorithm Time Complexity

Complexity analysis for dijkstra's algorithm with adjacency matrix representation of graph.

Time complexity of Dijkstra's algorithm is $O(V^2)$ where V is the number of verices in the graph.

It can be explained as below:

1. First thing we need to do is find the unvisited vertex with the smallest path. For that we require $O(V)$ time as we need check all the vertices.
2. Now for each vertex selected as above, we need to relax its neighbours which means to update each neighbours path to the smaller value between its current path or to the newly found. The time required to relax one neighbour comes out to be of order of O(1) (constant time).
3. For each vertex we need to relax all of its neighbours, and a vertex can have at most V-1 neighbours, so the time required to update all neighbours of a vertex comes out to be [O(V) * O(1)] = O(V)

So now following the above conditions, we get:

Time for visiting all vertices =O(V)

Time required for processing one vertex=O(V)

Time required for visiting and processing all the vertices

$= O(V)*O(V) =O(V^2)$

So the time complexity of dijkstra's algorithm using adjacency matrix representation comes out to be $O(V^2)$

Space complexity of adajacency matrix representation of graph in the algorithm is also $O(V^2)$ as a V*V matrix is required to store the representation of the graph. An additional array of V length will also be used by the algortihm to maintain the states of each vertex but the total space complexity will remain O$(V^2)$.

The time complexity of dijkstra's algorithm can be reduced to O((V+E)logV) using adjacency list representation of the graph and a min-heap to store the unvisited vertices, where E is the number of edges in the graph and V is the number of vertices in the graph.

With this implementation, the time to visit each vertex becomes O(V+E) and the time required to process all the neighbours of a vertex becomes O(logV).

Time for visiting all vertices =O(V+E)

Time required for processing one vertex=O(logV)

Time required for visiting and processing all the vertices

$= O(V+E)*O(logV) = O((V+E)logV)$

The space complexity in this case will also improve to O(V) as both the adjacency list and min-heap require O(V) space. So the total space complexity becomes

$O(V)+O(V)=O(2V) = O(V)$

Proof of Correctness

The main assertion on which Dijkstra's algorithm correctness is based is the following:

After any vertex v becomes marked, the current distance to it d[v] is the shortest, and will no longer change.

Let assume

• dijkstra(s,t) to be the shortest distance between two nodes s and t as calculated by dijksta's algorithm
• shortest(s,t) to be the actual shortest distance between two nodes s and t.

Now our proposition is:

dijkstra(s,t)=shortest(s,t) for a vertex t that has been visited

Now we will prove this proposition by contradiction.

So let's assume that our above proposition is false.

dijkstra(s,t)>shortest(s,t) for a vertex t that has been visited

Now assume vertex x to be the first visited vertex for which dijkstra(s,x)>shortest(s,x), so for all vertices z upto before x, dijkstra(s,z)>shortest(s,z)

Now assume vertex y to be a visited vertex on the real shortest path from source to x, and vertex z to be an unvisited vertex on the real shortest path from source to x.

We can conclude that:

But, sub path of a shortest path is also a shortest path which implies

shortest(s,x)=shortest(s,z)+shortest(z,x)

We can now conclude that:

This result is contradictory to our proposition dijkstra(s,t)>shortest(s,t)

So the statemant that the condition dijkstra(s,t)=shortest(s,t) is false is false, our statement dijkstra(s,t)=shortest(s,t) is true.

Hence we have proved that the dijkstra's algorithm path will be the shortest path to any vertex.

Applications of Dijkstra Algorithm

Dijkstra's algorithm has many applications:

1. Digital Mapping Services like Google Maps: Suppose you want to travel from one city to another city. You use Google maps to find the shortest route. How will it work? Assume the city you are in to be the source vertex and your destination to be another vertex.

   There will still be many cities between your destination and starting point. Assume those cities to be intermediate vertices. The distance and traffic between any two cities can be assumed to be the weight between each pair of verices. Google maps will apply dijkstra algorithm on the city graph and find the shortest path.

2. Designate Servers: In a network, Dijkstra's Algorithm can be used to find the shortest path to a server for transmitting files amongst the nodes on a network.

3. IP Routing: Dijkstra's Algorithm can be used by link state routing protocols to find the best path to route data between routers.

Join our Data Structures in C++ Course now and gain a competitive edge in your programming career!

See More

• Dijkstra Algorithm Python

• Dijkstra's Algorithm Java