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.

Introduction to Dijkstra’s Algorithm

Dijkstra’s algorithm is one of the SSP (single source smallest path) algorithm that finds the shortest path from a source vertex to all vertices in a weighted graph.

The shortest path is the path with the lowest total cost.

Dijkstra’s algorithm works by relaxing the edges of the graph. It updates the cost of all vertices associated with a Vertex V, only if those costs can be improved.

How Dijkstra’s Algorithm Works?

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

We are given the following graph and 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 vertex as following:

Dijkstra shortest path algorithm

We know that the source vertex is ‘A’, so the distance from A to itself is 0 and for the rest of the vertices is infinite (∞) because in starting we don’t know if other vertices are connected to the source vertex.

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 with a 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++

Then we select the unvisited vertex with the least distance value. In our case, it’s vertex ‘B’ because it has a distance value of 10 whereas vertex ‘C’ has a distance value of 30.

Then we repeat the same process that we did with ‘A’ but this time we do not relax the distance value of the edge connected to the visited vertex (i.e. a).

We check if the distance of ‘C’ is less than the distance of ‘B’ + connecting edge weight. It is so we update the distance value of vertex ‘C’.

dijkstra shortest path algorithm example

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

So now the only unvisited vertex is vertex ‘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 that vertex.

dijkstra's algorithm program code

To know the path we trace the preceding vertices that were used to update the distance value of the vertices included in the path.

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

In Dijkstra’s algorithm, we choose the unvisited vertex which has the least distance value. So it is totally right to say that Dijkstra’s Algorithm uses the greedy approach.

For the relaxation purpose, we compare the distance value of the vertex with the sum of the distance value of the current vertex and the weight of the connecting edge.

It is important to note that we are using the distance value of the current vertex that was calculated and updated earlier. We are not calculating it from starting vertex ‘A’ again.

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

Hence, it would not be wrong to say that Dijkstra’s algorithm uses both dynamic programming and greedy approach.

Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm among the connected vertices chooses the one that has the least distance value. Therefore in programming, we use a priority queue data structure to get arrange vertices based on their distance value.

Using priority queue we can implement Dijkstra’s algorithm in following steps:

  1. Initialize distance of the source vertex with 0 and rest of the vertices with +∞.
  2. Add source vertex to the priority queue.
  3. Until the queue is empty:
    1. Fetch the vertex from the top of the queue.
    2. Visit all the unvisited vertices connected with the current vertex:
      1. Check if the distance of the vertex can be relaxed.
        1. If yes then update the distance value of the connected vertex.
        2. Also, update its predecessor with the current vertex.
        3. Add the vertex to the queue.
    3. Mark the vertex as visited and remove it from the queue.

Here is the implementation of the algorithm in C++ and Java:

C++

Java

Output:

A B C

In the above program, the priority queue is keeping track of all unvisited vertices. We had explicitly declared compare class to compare vertices based on their distance value. Therefore the vertex with the least distance will be placed at the top of the queue.

Each vertex has a predecessor that references the preceding vertex (vertex whose value has been used along with edge weight to update the distance value of the current vertex).

Every time we update the distance value of any vertex we also update its preceding vertices. We use it to trace the path from the destination to the source vertex.

Overview of Dijkstra’s Shortest Path Algorithm

  • The time complexity of Dijkstra’s algorithm is O(V + E . log(V)), where V is the number of vertices, and E is the number of edges in the graph.
  • Dijkstra’s algorithm may not perform best in dense graphs (i.e., graphs where E is close to V2).
  • Dijkstra’s algorithm fails to compute the shortest path in a graph with negative-weighted edges or cycle – Why?

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

15 − 6 =