Dijkstra’s Shortest Path Algorithm

Algorithm

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

#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 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

Your email address will not be published. Required fields are marked *