Dijkstra’s algorithm is one the dynamic programming algorithm used to find shortest path between two vertex in the graph or tree.

What is Dijkstra Algorithm?

To understand Dijkstra’s algorithm, let’s see its working on this example.

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

Dijkstra's algorithm

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

Dijkstra shortest path algorithm

Now one by one, we check for the vertices connected to ‘A‘, whether the current distance value is less than from 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 doing this 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 distance value of connected 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 our last 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 Algorithm C++ Program

Now we need to implement all the steps which we have discussed into Program.

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

C++

Java

Note: In the above program we priority queue is keeping track of all unvisited vertices. Hence, on discovering the connected vertices we are pushing them to the queue. Also on tracing back from final vertex to source vertex we formed 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

That’s all we need to do in order to find the shortest path using Dijkstra’s algorithm. If you have any doubts then do comment below.

Leave a Reply

Close Menu