Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a greedy approach with a priority queue.

When to Use

Finding shortest path in weighted graphs
All edge weights are non-negative
Single-source shortest path problems
Problems involving minimum cost or distance

Common Patterns

Standard Dijkstra

Uses priority queue to always process nearest unvisited node

Example: Network delay time, cheapest flights

Modified Dijkstra

Adapted for state-space graphs or multi-dimensional problems

Example: Shortest path with constraints, k-stops problems

Code Templates

Python

import heapq
from collections import defaultdict

def dijkstra(graph, start, n):
    # graph[u] = [(v, weight), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # Skip if we've found better path
        if d > dist[u]:
            continue
        
        # Relax edges
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    return dist

C++

#include <vector>
#include <queue>
#include <utility>
using namespace std;

vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    
    // Priority queue: {distance, node}
    priority_queue<pair<int, int>, 
                   vector<pair<int, int>>, 
                   greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        // Skip if we've found better path
        if (d > dist[u]) continue;
        
        // Relax edges
        for (auto [v, weight] : graph[u]) {
            int newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }
    
    return dist;
}