Dijkstra's Algorithm

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?

Initialization

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

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.

Selection

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

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.

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;
}

#dijkstra.py
import heapq

def dijkstra(adj, src):
 size = len(adj)
 visited = [False] * size
 dist = [float('inf')] * size
 dist[src] = 0
 
 while True:
     node = -1
     mini = float('inf')
     for i in range(size):
         if not visited[i] and dist[i] < mini:
             node = i
             mini = dist[i]
     
     if node == -1:
         break
         
     visited[node] = True
     for neighbor, weight in adj[node]:
         if not visited[neighbor] and dist[node] + weight < dist[neighbor]:
             dist[neighbor] = dist[node] + weight
 
 return dist

# Example usage
if __name__ == "__main__":
 n = 5
 adj = [[] for _ in range(n)]
 adj[0].append((1, 2))
 adj[0].append((2, 4))
 adj[1].append((2, 1))
 adj[1].append((3, 7))
 adj[2].append((4, 3))
 adj[3].append((4, 1))
 
 src = 0
 distances = dijkstra(adj, src)
 print(f"Shortest distances from node {src}:")
 for i in range(n):
     print(f"Node {i}: {distances[i]}")

// dijkstra.js
function dijkstra(adj, src) {
 const size = adj.length;
 const visited = new Array(size).fill(false);
 const dist = new Array(size).fill(Infinity);
 dist[src] = 0;
 
 while (true) {
     let node = -1;
     let mini = Infinity;
     
     for (let i = 0; i < size; i++) {
         if (!visited[i] && dist[i] < mini) {
             node = i;
             mini = dist[i];
         }
     }
     
     if (node === -1) break;
     
     visited[node] = true;
     for (const [neighbor, weight] of adj[node]) {
         if (!visited[neighbor] && dist[node] + weight < dist[neighbor]) {
             dist[neighbor] = dist[node] + weight;
         }
     }
 }
 
 return dist;
}

// Example usage
const n = 5;
const adj = Array.from({ length: n }, () => []);
adj[0].push([1, 2]);
adj[0].push([2, 4]);
adj[1].push([2, 1]);
adj[1].push([3, 7]);
adj[2].push([4, 3]);
adj[3].push([4, 1]);

const src = 0;
const distances = dijkstra(adj, src);
console.log(`Shortest distances from node ${src}:`);
for (let i = 0; i < n; i++) {
 console.log(`Node ${i}: ${distances[i]}`);
}

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;
}

#dijkstra.py
import heapq

def dijkstra(adj, src):
 size = len(adj)
 visited = [False] * size
 dist = [float('inf')] * size
 dist[src] = 0
 pq = [(0, src)]  # (distance, node)

 while pq:
     current_dist, node = heapq.heappop(pq)
     if visited[node]:
         continue
     visited[node] = True

     for neighbor, weight in adj[node]:
         if not visited[neighbor] and current_dist + weight < dist[neighbor]:
             dist[neighbor] = current_dist + weight
             heapq.heappush(pq, (dist[neighbor], neighbor))

 return dist

# Example usage
if __name__ == "__main__":
 n = 5
 adj = [[] for _ in range(n)]
 adj[0].append((1, 2))
 adj[0].append((2, 4))
 adj[1].append((2, 1))
 adj[1].append((3, 7))
 adj[2].append((4, 3))
 adj[3].append((4, 1))
 
 src = 0
 distances = dijkstra(adj, src)
 print(f"Shortest distances from node {src}:")
 for i in range(n):
     print(f"Node {i}: {distances[i]}")

//dijkstra.js
class MinHeap {
 constructor() {
     this.heap = [];
 }
 
 push(val) {
     this.heap.push(val);
     this.bubbleUp();
 }
 
 pop() {
     if (this.heap.length === 1) return this.heap.pop();
     const min = this.heap[0];
     this.heap[0] = this.heap.pop();
     this.bubbleDown();
     return min;
 }
 
 isEmpty() {
     return this.heap.length === 0;
 }
 
 bubbleUp() {
     let idx = this.heap.length - 1;
     while (idx > 0) {
         let parentIdx = Math.floor((idx - 1) / 2);
         if (this.heap[parentIdx][0] <= this.heap[idx][0]) break;
         [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
         idx = parentIdx;
     }
 }
 
 bubbleDown() {
     let idx = 0;
     while (2 * idx + 1 < this.heap.length) {
         let leftIdx = 2 * idx + 1;
         let rightIdx = 2 * idx + 2;
         let smallestIdx = leftIdx;
         
         if (rightIdx < this.heap.length && this.heap[rightIdx][0] < this.heap[leftIdx][0]) {
             smallestIdx = rightIdx;
         }
         
         if (this.heap[idx][0] <= this.heap[smallestIdx][0]) break;
         [this.heap[idx], this.heap[smallestIdx]] = [this.heap[smallestIdx], this.heap[idx]];
         idx = smallestIdx;
     }
 }
}

function dijkstra(adj, src) {
 const size = adj.length;
 const visited = new Array(size).fill(false);
 const dist = new Array(size).fill(Infinity);
 dist[src] = 0;
 const pq = new MinHeap();
 pq.push([0, src]); // [distance, node]

 while (!pq.isEmpty()) {
     const [currentDist, node] = pq.pop();
     if (visited[node]) continue;
     visited[node] = true;

     for (const [neighbor, weight] of adj[node]) {
         if (!visited[neighbor] && currentDist + weight < dist[neighbor]) {
             dist[neighbor] = currentDist + weight;
             pq.push([dist[neighbor], neighbor]);
         }
     }
 }

 return dist;
}

// Example usage
const n = 5;
const adj = Array.from({ length: n }, () => []);
adj[0].push([1, 2]);
adj[0].push([2, 4]);
adj[1].push([2, 1]);
adj[1].push([3, 7]);
adj[2].push([4, 3]);
adj[3].push([4, 1]);

const src = 0;
const distances = dijkstra(adj, src);
console.log(`Shortest distances from node ${src}:`);
for (let i = 0; i < n; i++) {
 console.log(`Node ${i}: ${distances[i]}`);
}

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.

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.

Dijkstra's Algorithm

On this page