Dijkstra's Algorithm

Time complexity: O((V + E) log V)

Space complexity: O(V)

Data type: Graphs

Visualization

React Flow
Click any two vertices to connect them
Shift+click on the node to set it as "start"
Shift+click on arrow to increase weight
Ctrl+click on arrow to decrease weight

Definition

Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest-path tree. It finds the minimum distance from a starting node to all other nodes in the graph.

Constraints

  • Requires non-negative edge weights (fails with negative weights)
  • Optimal for graphs with reasonable edge density
  • Not suitable for graphs with negative cycles (use Bellman-Ford instead)
  • Performance degrades for very large sparse graphs

Step-by-step explanation

Arguments:

  • Graph representation - graph
  • Starting node - source
  • Distance array - dist[]
  • Priority queue/min-heap - priorityQueue
  • Visited nodes set - visited

Explanation:

  • Initialize all distances as INFINITY except the source node (distance 0)
  • While there are unvisited nodes:
    • Select the unvisited node with the smallest known distance
    • For each neighbor of the current node:
      • Calculate tentative distance through current node
      • Update neighbor's distance if tentative distance is smaller
    • Mark current node as visited
  • After processing all nodes, dist[] contains shortest distances from source

Returns:

Returns a distance array where each index represents the shortest distance from the source node
Can optionally return a predecessor array to reconstruct paths
Returns null if negative weights are detected

Example

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <limits>
5


6
const int INF = std::numeric_limits<int>::max();
7


8
void dijkstra(const std::vector<std::vector<std::pair<int, int>>>& graph, int source, std::vector<int>& distance) {
9
    int n = (int)graph.size();
10
    distance.assign(n, INF);
11
    distance[source] = 0;
12


13
    using pii = std::pair<int, int>; // (distance, vertex)
14
    std::priority_queue<pii, std::vector<pii>, std::greater<>> pq;
15
    pq.push({0, source});
16


17
    while (!pq.empty()) {
18
        int dist = pq.top().first;
19
        int u = pq.top().second;
20
        pq.pop();
21


22
        if (dist > distance[u]) continue;
23


24
        for (auto [v, weight] : graph[u]) {
25
            if (distance[u] + weight < distance[v]) {
26
                distance[v] = distance[u] + weight;
27
                pq.push({distance[v], v});
28
            }
29
        }
30
    }
31
}