Dijkstra's Algorithm

Algorithm for finding the shortest path from source to destination

Introduction

Dijkstra Algorithm is a famous algorithm used to solve the single-source shortest path problem for a graph with non-negative edge weights. A graph consists of vertices (or nodes) connected by edges (or lines). In simple terms, it helps to find the quickest or least costly way from one point to another in a network, like finding the fastest route on a map.

How Dijkstra Algorithm Works?

1

Initialization

  • Set the distance to the source node to 0 and all other node distances to infinity (∞).
  • Set all nodes as unvisited.
2

Relaxation

  • Starting from the source node, consider all its neighbors. Calculate the distance through the current node to each of its neighbors.
  • If the calculated distance of a neighbor is less than its current assigned value, update its distance.
3

Selection

  • From the unvisited nodes, select the node with the smallest tentative distance.
4

Termination

  • The algorithm terminates when all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity, indicating that no path exists.
Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7
Carousel image 8
Carousel image 9

Implementation

//dijkstra.cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> dijkstra(vector<vector<pair<int, int>>> adj, int src) {
int size = adj.size();
vector<bool> visited(size, false);
vector<int> dist(size, INT_MAX);
dist[src] = 0;

while (true) {
    int node = -1;
    int mini = INT_MAX;
    for (int i = 0; i < size; i++) {
        if (!visited[i] && dist[i] < mini) {
            node = i;
            mini = dist[i];
        }
    }
    
    if (node == -1) break;
    
    visited[node] = true;
    for (auto& neighbor : adj[node]) {
        int neighborNode = neighbor.first;
        int weight = neighbor.second;
        if (!visited[neighborNode] && dist[node] + weight < dist[neighborNode]) {
            dist[neighborNode] = dist[node] + weight;
        }
    }
}

return dist;
}
int main() {
int n = 5;
vector<vector<pair<int, int>>> adj(n);
adj[0].push_back({1, 2});
adj[0].push_back({2, 4});
adj[1].push_back({2, 1});
adj[1].push_back({3, 7});
adj[2].push_back({4, 3});
adj[3].push_back({4, 1});
int src = 0;
vector<int> distances = dijkstra(adj, src);
cout << "Shortest distances from node " << src << ":\n";
for (int i = 0; i < n; i++) {
    cout << "Node " << i << ": " << distances[i] << endl;
}
return 0;
}

Time Complexity

  • For each node, you are performing an O(V) operation to find the node with the minimum distance.
  • Since there are V nodes, the total time complexity becomes O(V^2).

Time Complexity: O(V^2)

Space Complexity

  • The space required for the dist and visited arrays. Both arrays are of size V, resulting in O(V) space.

Space Complexity: O(V)

Optimization Using Priority Queue

//dijkstra.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> dijkstra(vector<vector<pair<int, int>>> adj, int src)
{
  int size = adj.size();
  vector<bool> visited(size, false);
  vector<int> dist(size, INT_MAX);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p;
  p.push({0, src});
  dist[src] = 0;

  while (!p.empty())
  {
      int node = p.top().second;
      p.pop();
      if (visited[node])
          continue;
      visited[node] = true;
      for (int i = 0; i < adj[node].size(); i++)
      {
          int neighbor = adj[node][i].first;
          int weight = adj[node][i].second;
          if (!visited[neighbor] && dist[node] + weight < dist[neighbor])
          {
              dist[neighbor] = dist[node] + weight;
              p.push({dist[neighbor], neighbor});
          }
      }
  }

  return dist;
}

int main()
{
  int n = 5;
  vector<vector<pair<int, int>>> adj(n);
  adj[0].push_back({1, 2});
  adj[0].push_back({2, 4});
  adj[1].push_back({2, 1});
  adj[1].push_back({3, 7});
  adj[2].push_back({4, 3});
  adj[3].push_back({4, 1});
  int src = 0;
  vector<int> dist = dijkstra(adj, src);

  cout << "Shortest distances from node " << src << ":\n";
  for (int i = 0; i < dist.size(); i++)
  {
      cout << "Node " << i << ": " << dist[i] << endl;
  }

  return 0;
}

Time Complexity :Priority Queue

  • The initialization of the dist and visited arrays takes O(V).

  • Priority Queue Operations

    • For each node, we perform a pop operation from the priority queue, which takes O(logV)time.

    • For each neighbor of a node, we perform an insert operation (push) into the priority queue. In the worst case, this happens for every edge, so we can have at most E insertions, where E is the number of edges in the graph. Each insert operation also takes O(logV).

Time Complexity : O((V+E)logV)
where,
V is the number of vertices.
E is the number of edges.

Space Complexity :Priority Queue

  • The space required for the dist and visited arrays. Both arrays are of size V, resulting in O(V) space.
  • In the worst case, all vertices might be stored in the priority queue at once, so it requires O(V) space.

Space Complexity : O(V)

Limitation

Dijkstra's Algorithm fails when there are negative weight edges.

Why Does It Fail?

Greedy Approach

  • Dijkstra picks the currently known shortest path and marks the node as finalized (i.e., it won’t be updated again).
  • If a negative edge appears after a node is finalized, the algorithm does not revisit it, leading to incorrect results.
Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6

From the above example, we see that Dijkstra's Algorithm fails for negative edges. To overcome this limitation of Dijkstra's Algorithm, the Bellman-Ford Algorithm comes to the rescue.