Dijkstra’s algorithm

Last Updated on February 8, 2024 by Abhishek Sharma

Dijkstra’s algorithm, named after Dutch computer scientist Edsger W. Dijkstra, is a fundamental algorithm used in graph theory and computer science for finding the shortest path between nodes in a graph with non-negative edge weights. Originally designed to solve the single-source shortest path problem, Dijkstra’s algorithm efficiently determines the shortest path from a designated starting node to all other nodes in the graph. Its simplicity and effectiveness make it a widely used tool in various applications, including network routing protocols, transportation networks, and data processing systems.

How Dijkstra algorithm Work?

The algorithm works by maintaining a set of vertices that have already been visited, and a set of vertices that have not yet been visited. The algorithm starts at the source vertex and adds it to the set of visited vertices. Then, it repeatedly finds the vertex in the set of unvisited vertices that has the shortest known path to the source vertex, and adds that vertex to the set of visited vertices. This process continues until all vertices have been visited.

The Dijkstra algorithm is a greedy algorithm, which means that it makes the best possible choice at each step, without considering the future consequences of its decisions. In the case of Dijkstra algorithm, the best possible choice is to add the vertex with the shortest known path to the source vertex to the set of visited vertices.

The Dijkstra algorithm is a very efficient algorithm for finding the shortest paths in a graph. Its time complexity is O(V log V), where V is the number of vertices in the graph.

Example of Dijkstra algorithm

Here is an example of Dijkstra algorithm that is discussed below.

Step 1 : Start with a weighted graph.

Step 2 : Choose a starting vertex and assign infinity path values to all other devices.

Step 3 : Go to each vertex and update its path length.

Step 4 : If the path length of the adjacent vertex is less than new path length, don’t update it.

Step 5 : Avoid updating path lengths of already visited vertices.

Step 6 : After each iteration, we pick the unvisited vertex with the least path length. So we choose 5.

Step 7 : Notice how the rightmost vertex has its path length updated twice.

Step 8 : Repeat until all the vertices have been visited.

Pseudocode for Dijkstra algorithm

The following is a pseudocode for Dijkstra algorithm:

procedure Dijkstra(G, s)
    for each vertex v in G
        dist[v] := infinity
        prev[v] := nil
    dist[s] := 0
    Q := {s}
    while Q is not empty
        u := vertex in Q with minimum dist[u]
        remove u from Q
        for each vertex v adjacent to u
            if dist[v] > dist[u] + weight(u, v)
                dist[v] := dist[u] + weight(u, v)
                prev[v] := u

In this pseudocode, G is the graph, s is the source vertex, dist[v] is the shortest known path from s to vertex v, and prev[v] is the predecessor of vertex v in the shortest path from s to v.

Code Implementation of Dijkstra algorithm

Here is a code implementation of the Dijkstra algorithm in C++.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// A structure to represent a weighted edge
struct Edge {
  int src;
  int dest;
  int weight;
};

// A class to represent a graph
class Graph {
private:
  int V; // number of vertices
  vector<vector<Edge>> adj; // adjacency list

public:
  Graph(int V) {
    this->V = V;
    adj.resize(V);
  }

  void addEdge(int src, int dest, int weight) {
    Edge edge{src, dest, weight};
    adj[src].push_back(edge);
  }

  // Dijkstra's algorithm
  void dijkstra(int src, vector<int>& dist) {
    // Initialize the distance array
    dist.resize(V, INT_MAX);

    // Create a priority queue to store the vertices
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // Add the source vertex to the priority queue
    pq.push({0, src});

    // Mark the source vertex as visited
    dist[src] = 0;

    while (!pq.empty()) {
      // Get the vertex with the shortest distance
      int u = pq.top().second;
      pq.pop();

      // Mark the vertex as visited
      visited[u] = true;

      // For each unvisited neighbor of u
      for (Edge edge : adj[u]) {
        int v = edge.dest;

        // If the distance to v is greater than the distance to u plus the weight of the edge
        if (dist[v] > dist[u] + edge.weight) {
          // Update the distance to v
          dist[v] = dist[u] + edge.weight;

          // Add v to the priority queue
          pq.push({dist[v], v});
        }
      }
    }
  }
};

int main() {
  // Create a graph
  Graph g(5);

  // Add edges to the graph
  g.addEdge(0, 1, 1);
  g.addEdge(0, 2, 4);
  g.addEdge(1, 2, 2);
  g.addEdge(1, 3, 7);
  g.addEdge(2, 3, 3);
  g.addEdge(2, 4, 5);
  g.addEdge(3, 4, 2);

  // Initialize the distance array
  vector<int> dist(g.V, INT_MAX);

  // Run Dijkstra's algorithm
  g.dijkstra(0, dist);

  // Print the shortest distances from vertex 0 to all other vertices
  for (int i = 0; i < g.V; i++) {
    cout << "Shortest distance from vertex 0 to vertex " << i << " is " << dist[i] << endl;
  }

  return 0;
}

Explanation : This code first creates a graph object with 5 vertices. Then, it adds edges to the graph. Next, it initializes the distance array to INT_MAX, which represents infinity. Finally, it runs Dijkstra’s algorithm and prints the shortest distances from vertex 0 to all other vertices.

Applications of Dijkstra algorithm

Dijkstra algorithm is extremely versatile and has a wide range of applications. Among its most common applications are:

• Routing in computer networks
• Finding the shortest path between two points in a road network
• Finding the shortest path between two genes in a DNA sequence
• Finding the shortest path between two products in a supply chain
• Finding the shortest path between two servers in a cloud computing environment

Dijkstra algorithm is also used in a variety of other applications, such as:

• Finding the best route for a robot to navigate through a factory
• Finding the best way to schedule tasks in a manufacturing process
• Finding the best way to allocate resources in a computer system

Complexity of Dijkstra algorithm

The time complexity of Dijkstra algorithm is O(V log V), where V is the number of vertices in the graph. The space complexity of the algorithm is O(V), where V is the number of vertices in the graph.

Some Variations of Dijkstra algorithm

There are many variations of Dijkstra algorithm. Some of the most common variations include:

• The Bellman-Ford algorithm, which is a more general algorithm that can be used to find the shortest paths in graphs with negative weights.
• The Floyd-Warshall algorithm, which is a more efficient algorithm for finding the shortest paths in graphs with dense connectivity.

The algorithm is a more sophisticated algorithm that can be used to find the shortest paths in graphs with obstacles.

Conclusion
In conclusion, Dijkstra’s algorithm stands as a cornerstone in the field of graph theory and computer science, offering an elegant solution to the single-source shortest path problem. Its efficiency and versatility have made it a vital component in the development of various real-world applications, facilitating optimal routing, resource allocation, and decision-making processes. As technology continues to evolve, Dijkstra’s algorithm remains a timeless algorithm, embodying the essence of computational efficiency and problem-solving prowess.

Frequently Asked Questions (FAQs) related to the Dijkstra Algorithm

Here are some frequently asked questions about Dijkstra algorithm.

1. What is the single-source shortest path problem, and how does Dijkstra’s algorithm solve it?
The single-source shortest path problem involves finding the shortest paths from a designated starting node to all other nodes in a graph. Dijkstra’s algorithm efficiently solves this problem by iteratively exploring the graph from the starting node, updating the shortest path distances to each node as it progresses.

2. What are the key characteristics of Dijkstra’s algorithm?
Dijkstra’s algorithm is known for its simplicity, efficiency, and effectiveness in finding shortest paths in graphs with non-negative edge weights. It employs a greedy approach, selecting the node with the smallest tentative distance at each step and updating the shortest path distances accordingly.

3. What is the time complexity of Dijkstra’s algorithm?
The time complexity of Dijkstra’s algorithm depends on the implementation and the data structures used. In the simplest form, with an adjacency matrix representation, the time complexity is O(V^2), where V is the number of vertices in the graph. However, with a more efficient implementation using a priority queue, the time complexity can be reduced to O((V + E) log V), where E is the number of edges.

4. Does Dijkstra’s algorithm work for graphs with negative edge weights?
No, Dijkstra’s algorithm does not work for graphs with negative edge weights. This is because it relies on the assumption that all edge weights are non-negative. If negative edge weights are present, Dijkstra’s algorithm may produce incorrect results or enter into an infinite loop.

5. How can I implement Dijkstra’s algorithm in my programming projects?
Dijkstra’s algorithm can be implemented in various programming languages using different data structures such as arrays, priority queues, or adjacency lists. There are numerous online resources, tutorials, and libraries available to help with the implementation of Dijkstra’s algorithm in different programming environments.