Summary: In this tutorial, we will learn what is Dijkstra Shortest Path Algorithm and how to implement the Dijkstra Shortest Path Algorithm in C++ and Java to find the shortest path between two vertices of a graph.

What is Dijkstra Shortest Path Algorithm?

Dijkstra’s algorithm is a dynamic programming algorithm which is used to find the shortest path between two vertexes of the graph or tree.

To understand Dijkstra’s algorithm, let’s consider the following example.

We are given the following graph and we need to find the shortest path from vertex ‘A’ to vertex ‘C’.

Dijkstra's algorithm

To find the shortest path using Dijkstra’s algorithm, we first initialize the distance of each vertices from the source vertices as following:

Dijkstra shortest path algorithm

We know that the source vertex is ‘A‘, so the distance from A to itself is zero (0) and for the rest of the vertices is infinity () because in starting we don’t know whether others vertices are connected with the source vertex or not.

Now one by one, we check for the vertices connected to ‘A‘, whether the current distance value is < the distance of ‘A + connecting edge weight.

If yes then we update the distance value of the connected vertices to lower value, else not. And after completing this process with all connected vertices, we mark ‘A’ as visited so that we don’t visit it again.

dijkstra's algorithm c++

Now we select the unvisited vertex with the least distance, to do same operation on it. In our case its vertex ‘B‘ because it has distance value of 10 whereas vertex ‘C‘ has distance value of 30.

Again we repeat the same process which we had done earlier with ‘A‘ but this time we don’t need to do correction on the distance value of the visited vertex (i.e. A). So only left vertex is ‘C‘.

If the distance of ‘C‘ is less than the distance of ‘B+ connecting edge weight, then update the distance value.

dijkstra shortest path algorithm example

We have to repeat the process for every vertex until none is left.

So now we select the last unvisited vertex i.e. C.

Since vertex ‘C’ has no connected unvisited vertex, so we mark it visited.

Now, the distance value of each vertex is the distance from ‘A’ to itself.

dijkstra's algorithm program code

To know the path we trace back from the final vertex to the vertex which was used to update the distance value, till we reach the starting vertex.

Is Dijkstra’s Algorithm a Greedy Algorithm or a Dynamic Programming Algorithm?

After visiting a vertex we choose another unvisited vertex having the least distance value. So it is totally right to say that Dijkstra’s Algorithm uses greedy approach to select or visit another vertex.

Also, we are comparing the distance value of the vertex with the sum of the distance value of the current vertex and edge weight of the connecting edge.

The most important point is to note that we are using the distance value of current vertex i.e B (distance from ‘A’) which we have calculated and updated earlier. We are not calculating it from starting vertex ‘A’ again.

Which proves that we are using memoized value i.e dynamic programming.

Hence, we can say that Dijkstra’s Algorithm uses both dynamic programming and greedy approach.

Dijkstra’s Shortest Path Algorithm

Here are some of the points that need to be followed to implement Dijkstra Shortest Path Algorithm:

  • To represent vertex. we use class.
  • To represent edge, we use class
  • To select the next unvisited vertex with the least distance, we use a priority queue. We explicitly declared compare class to compare two vertices on the basis of their distance value. Therefore the vertex with the least distance will be placed at the top of the queue.
  • Each vertex has a predecessor, which is updated each time we update the distance value.
  • The predecessor is basically the pointer which will point to that vertex whose value has been used along with edge weight to update the distance value of the current vertex. Hence it will be helpful in tracing back the path.

C++

Java

Note: In the above program, the priority queue is keeping track of all unvisited vertices. Hence, on discovering the unvisited connected vertices we push them to the queue. Also, in the trace back process from the final vertex to the source vertex, we formed a reversed list, hence we need to reverse it before outputting the resultant path.

Output

For the given graph:

Dijkstra's algorithm
Dijkstra's algorithm program output

In this tutorial, we learned what is Dijkstra’s Shortest Path Algorithm and how to implement Dijkstra’s Shortest Path Algorithm in C++ and Java to find the shortest path between two vertices of a graph.

Leave a Reply