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’.
To find the shortest path using Dijkstra’s algorithm, we first initialize the distance of each vertices from the source vertex as following:
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.
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’.
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.
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:
- Initialize distance of the source vertex with 0 and rest of the vertices with +∞.
- Add source vertex to the priority queue.
- Until the queue is empty:
- Fetch the vertex from the top of the queue.
- Visit all the unvisited vertices connected with the current vertex:
- Check if the distance of the vertex can be relaxed.
- If yes then update the distance value of the connected vertex.
- Also, update its predecessor with the current vertex.
- Add the vertex to the queue.
- Check if the distance of the vertex can be relaxed.
- Mark the vertex as visited and remove it from the queue.
Here is the implementation of the algorithm in C++ and Java:
C++
#include <iostream>
#include <list>
#include <limits>
#include <queue>
using namespace std;
//Edge class declared early so that,
//it is available for use in Vertex class
class Edge;
class Vertex{
public:
//vertex label
char name;
//Distance value
double distance = numeric_limits<double>::infinity();
//To mark it visited
bool visited = false;
//Edges connected to the vertex, will lead to next vertex
list<Edge*> adjacentEdge;
//distance value updated by which vertex
Vertex* predecessor = nullptr;
Vertex(char name){
this->name = name;
}
//method to add connect edge with current vertex
void addAdjacentEdge(Edge* e){
adjacentEdge.push_back(e);
}
};
//Will return true if v1's distance < v2's distance
//Will be used by priority queue
class Compare{
public:
bool operator()(Vertex *v1, Vertex *v2){
return v1->distance < v2->distance? true : false;
}
};
class Edge{
public:
Vertex *from;
Vertex *to;
int weight;
Edge(Vertex* s, Vertex* t, int w){
this->from = s;
this->to = t;
this->weight = w;
}
};
class DijkstraAlgorithm{
public:
Vertex *source;
priority_queue<Vertex*, vector<Vertex*>, Compare> vertexQueue;
DijkstraAlgorithm(Vertex *s){
this->source = s;
}
//main function to implement Dijkstra's Algorithm
void computePath(){
source->distance = 0; //Starting vertex distance should be 0
list<Edge*> :: iterator eit; //Iterator to iterate through edges
vertexQueue.push(source);
//run algorithm until queue is empty
while(!vertexQueue.empty()){
//get vertex from the top of the queue
//i.e. vertex with least distance
Vertex* current_vertex = vertexQueue.top();
for(Edge* edge: current_vertex->adjacentEdge){
Vertex *v = edge->to;
//Check if vertex is not visited
if( !v->visited){
//Update its distance with the lowest value
if(current_vertex->distance + edge->weight < v->distance){
v->distance = current_vertex->distance + edge->weight;
//also update the preceding vertex
v->predecessor = current_vertex;
vertexQueue.push(v);
}
}
}
//pop the current vertex from the queue
vertexQueue.pop();
//mark vertex as visited
current_vertex->visited = true;
}
}
//method to return shortest path in the form of a list
list<Vertex*> shortestPath(Vertex *d){
list<Vertex*> shortPath;
shortPath.push_front(d);
while(d->predecessor != nullptr){
shortPath.push_front(d->predecessor );
d = d->predecessor ;
}
return shortPath;
}
};
int main()
{
//vertices
Vertex* v[] = {new Vertex{'A'},new Vertex{'B'},new Vertex{'C'}};
//Edges
Edge* e[] = {new Edge{v[0], v[1], 10}, new Edge{v[0], v[2], 30},new Edge{v[1], v[2], 10}};
//connect edges to the vertices
v[0]->addAdjacentEdge(e[0]);
v[0]->addAdjacentEdge(e[1]);
v[1]->addAdjacentEdge(e[0]);
v[1]->addAdjacentEdge(e[2]);
v[2]->addAdjacentEdge(e[1]);
v[2]->addAdjacentEdge(e[2]);
//Driver code
DijkstraAlgorithm da(v[0]);
da.computePath();
list<Vertex*> result= da.shortestPath(v[2]);
cout<< "Shortest Path: ";
for(Vertex* v: result){
cout << v->name<< " ";
}
return 0;
}Java
import java.util.*;
class Vertex implements Comparable<Vertex>{
//vertex label
String name;
//Distance value
double distance = Double.MAX_VALUE;
//to mark vertex as visited
boolean visited;
//Edges connected to the vertex, will lead to next vertex
List<Edge> adjacentEdge = new ArrayList<>();
//distance value is updated by which vertex
Vertex predecessor = null;
public Vertex(String n){
this.name = n;
}
public void addadjacentEdge(Edge e){
adjacentEdge.add(e);
}
//Function to compare two vertices on basis of diatance
//used by the priority queue
@Override
public int compareTo(Vertex b) {
return (int) (this.distance - b.distance);
}
@Override
public String toString(){
return this.name;
}
}
class Edge {
Vertex from;
Vertex to;
int weight;
public Edge(Vertex from, Vertex to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
class Dijkstra {
//source vertex
Vertex source;
//Priority queue to queue vertices w.r.t least distance
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();
public Dijkstra(Vertex source) {
this.source = source;
}
//Function implementing Dijkstra's Algorithm
void computePath(){
//Starting vertex distance should be 0
source.distance = 0;
//add source vertex to the queue
vertexQueue.add(source);
//run until queue is not empty
while(!vertexQueue.isEmpty()){
//Get vertex from the top of queue
//i.e. vertex with least distance
Vertex actualVertex = vertexQueue.peek();
//get adjacent vertices through connected edges
for(Edge edge: actualVertex.adjacentEdge){
Vertex v = edge.to;
//If not visited then check whether the distance value could be lower
if( !v.visited){
if(actualVertex.distance + edge.weight < v.distance){
v.distance = actualVertex.distance + edge.weight;
v.predecessor = actualVertex; //also update its predecessor
vertexQueue.add(v);
}
}
}
//remove vertex from queue
vertexQueue.poll();
//mark vertex as visited
actualVertex.visited = true;
}
}
//Function to return the shortest path
List<Vertex> shortestPath(Vertex v){
//list to hold path
List<Vertex> shortPath = new ArrayList<>();
//Trace route from the 'v' to the source vertex
shortPath.add(v);
while(v.predecessor != null){
shortPath.add(v.predecessor);
v = v.predecessor;
}
//reverse the list to correct the order
Collections.reverse(shortPath);
//return list
return shortPath;
}
}
public class Main {
public static void main(String args[]){
//Creating vertices
Vertex v[] = {new Vertex("A"),new Vertex("B"),new Vertex("C")};
//Creating Edges
Edge e[] = {new Edge(v[0],v[1],10),new Edge(v[0],v[2],30),new Edge(v[1],v[2],10)};
//Connecting vertex and edges
v[0].addadjacentEdge(e[0]);
v[0].addadjacentEdge(e[1]);
v[1].addadjacentEdge(e[0]);
v[1].addadjacentEdge(e[2]);
v[2].addadjacentEdge(e[1]);
v[2].addadjacentEdge(e[2]);
Dijkstra dijkstra = new Dijkstra(v[0]);
dijkstra.computePath();
List<Vertex> path= dijkstra.shortestPath(v[2]);
System.out.println("Shortest Path: ");
System.out.println(path);
}
}Output:
A B CIn 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.