Dijkstra's Shortest Path

Find shortest paths in weighted graphs.

Overview

Dijkstra's algorithm finds shortest path from source to all vertices.

Warning

Requires non-negative edge weights!

Complexity

Implementation	Time	Space
Binary Heap	\(O((V+E) \log V)\)	\(O(V)\)

Implementation

PythonC++

import heapq

def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph}
    distances[start] = 0
    pq = [(0, start)]
    visited = set()

    while pq:
        dist, node = heapq.heappop(pq)

        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

# Example
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8)],
    'D': []
}
print(dijkstra(graph, 'A'))

Click to expand solution code

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<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();

        if (d > dist[u]) continue;

        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

Algorithm Steps

1. Initialize distances to infinity (except source = 0)
2. Use priority queue for vertices
3. Extract minimum distance vertex
4. Update adjacent vertices
5. Repeat until queue empty

Applications

• GPS navigation
• Network routing (OSPF)
• Social networks
• Game pathfinding

Comparison

Algorithm	Edge Weights	Time
Dijkstra	Non-negative	\(O((V+E) \log V)\)
Bellman-Ford	Any	\(O(VE)\)
Floyd-Warshall	Any	\(O(V^3)\)