Dijkstra's Algorithm

Dijkstra's algorithm solves the single-source shortest paths problem on a weighted directed graph with nonnegative edge weights. It maintains a tentative distance from the source to every vertex and repeatedly extracts the unfinalized vertex with the smallest tentative distance, committing that distance as final and relaxing all its outgoing edges.

With a binary heap as the priority queue the classical implementation runs in $O((V + E) \log V)$. The nonnegativity of edge weights is what makes the "extract-min, commit, relax" strategy correct — the vertex we pop can never be made shorter by a later path, because any such path would have to go out to something already heavier and come back.

The solve function takes [n, edges, source] with edges as [u, v, w] triples and returns the distance array, using 10**18 for unreachable vertices.

Codes

Python

Original hand-rolled template:

import heapq

def dijk(s,e,adj,inf=10**9):
    # n=len(adj)
    pq=[(0,s)]
    d=[0]+[inf]*(n-1)
    while pq:
        # current node and current distance
        cd,c=heappop(pq)
        # remove stale edge updates
        if cd>d[c]:
            continue
        for nx,nw in adj[c]:
            # update better edges
            if d[nx]<=nw+cd:
                continue
            d[nx]=nw+cd
            # debug
            # print(nx,nw+cd)
            heappush(pq,(nw+cd,nx))
    # return final weight
    return d[e]

Cleaned up solve form:

import heapq

def solve(xs):
    """xs = [n, edges, source]. Return distances (10**18 for unreachable)."""
    n, edges, source = xs
    INF = 10**18
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [INF] * n
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                     # stale entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

C++

#include <queue>
#include <tuple>
#include <vector>

const long long INF = (long long)1e18;

std::vector<long long> dijkstra(int n,
        const std::vector<std::array<int, 3>>& edges, int source) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
    std::vector<long long> dist(n, INF);
    dist[source] = 0;
    using P = std::pair<long long, int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    pq.push({0, source});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            long long nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

Example

Loading Python runner...

Description

Dijkstra's algorithm is a greedy algorithm used to find the shortest path from a starting node to a target node in a weighted graph with non-negative edge weights.

It works by iteratively selecting the node with the smallest known distance from the start node,

updating the distances to its neighbors,

and repeating this process until the target node is reached or all reachable nodes have been processed.

Run time analysis

$O((V + E) \log V)$ with a binary heap. Each edge causes at most one push and one pop, both $O(\log V)$, and stale heap entries (entries for a vertex whose distance has already been improved) are filtered in $O(1)$. With a Fibonacci heap the bound improves to $O(E + V \log V)$.

Space analysis

$O(V + E)$. The adjacency list uses $O(V + E)$, the distance array is $O(V)$, and the heap may hold $O(E)$ entries at once because of stale pushes.

Proof of correctness

Let $\delta(s, v)$ denote the true shortest-path distance from the source $s$ to $v$. We prove by induction on the order in which vertices are popped from the priority queue that the first time a vertex $u$ is popped, the popped key $d$ satisfies $d = \delta(s, u)$, and the algorithm never changes $dist[u]$ afterwards.

Base case. The first vertex popped is $s$ with key $0$, and $\delta(s, s) = 0$.

Inductive step. Assume that every previously popped vertex $x$ was popped with key $\delta(s, x)$. Suppose the next pop is $u$ with key $d = dist[u]$, and toward a contradiction assume $d > \delta(s, u)$. Let $P$ be a shortest $s \to u$ path. Walk along $P$ from $s$ and let $y$ be the first vertex on $P$ that has not yet been popped (such $y$ exists because $u$ itself has not been popped yet). Let $x$ be the predecessor of $y$ on $P$; $x$ has been popped by assumption, with key $\delta(s, x)$. When $x$ was popped, the edge $(x, y)$ was relaxed, so at that moment $dist[y] \le \delta(s, x) + w(x, y) = \delta(s, y)$, and an entry $(\delta(s, y), y)$ was pushed onto the heap. Because edge weights are nonnegative and $y$ lies on a shortest path to $u$, we have $\delta(s, y) \le \delta(s, u) < d$. But then the heap contains an entry for $y$ with key strictly less than $d$, contradicting the fact that the min-priority queue chose $u$ with key $d$ next.

So $d = \delta(s, u)$. Once popped, $dist[u]$ can only be written if a relaxation strictly improves it, and no further relaxation can beat $\delta(s, u)$, so $dist[u]$ stays fixed. By induction, when the queue empties, $dist[v] = \delta(s, v)$ for every vertex reachable from $s$, and $dist[v] = \infty$ (encoded as $10^{18}$) for every unreachable one.

The argument breaks as soon as we allow a negative edge, because the claim $\delta(s, y) \le \delta(s, u)$ no longer holds — a later edge on $P$ could decrease the distance. This is why Dijkstra requires nonnegative weights.

Extensions

Applications

LeetCode 3650 [Expected difficulty: 7]

https://leetcode.com/problems/minimum-cost-path-with-edge-reversals/description

Details

Intuition

Simple graph construction, and imagine the reverse path as edge with double cost. Then run dijkstra to find the minimum cost path.

Every edge in the shortest path have only one edge flip, you may prove this by contradiction. So you don't need to worry about double switch on the same edge at all.

Solution

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        adj=collections.defaultdict(list)
        # no going back and traverse is equivalent to dijk
        for a,b,w in edges:
            adj[a].append((b,w))
            adj[b].append((a,w*2))
        inf=10**9
        def dijk(s,e,adj,inf=10**9):
            # n=len(adj)
            pq=[(0,s)]
            d=[0]+[inf]*(n-1)
            while pq:
                # current node and current distance
                cd,c=heappop(pq)
                # remove stale edge updates
                if cd>d[c]:
                    continue
                for nx,nw in adj[c]:
                    # update better edges
                    if d[nx]<=nw+cd:
                        continue
                    d[nx]=nw+cd
                    # debug
                    # print(nx,nw+cd)
                    heappush(pq,(nw+cd,nx))
            # return final weight
            return d[e]
        res=dijk(0,n-1,adj,inf)
        return res if res!=inf else -1

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 24 (Single-Source Shortest Paths).
• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1, 269-271.
• cp-algorithms — Dijkstra