Dijkstra's shortest path

Shortest distance from one node to every other node when edges have non-negative weights.

Time O((V + E) log V)Space O(V)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Always expand the closest node not yet finalised. Its distance cannot improve later, because any other route would pass through a node that is already farther away.

Code

C++PythonC#

unordered_map<char, int> dijkstra(
        unordered_map<char, vector<pair<char, int>>>& graph, char src) {
    unordered_map<char, int> dist;
    for (auto& [v, _] : graph) dist[v] = INT_MAX;
    dist[src] = 0;
    priority_queue<pair<int, char>, vector<pair<int, char>>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(graph: dict[str, list[tuple[str, int]]], src: str) -> dict[str, float]:
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

public static Dictionary<char, int> Dijkstra(
        Dictionary<char, List<(char to, int w)>> graph, char src) {
    var dist = graph.Keys.ToDictionary(v => v, _ => int.MaxValue);
    dist[src] = 0;
    var pq = new PriorityQueue<char, int>();
    pq.Enqueue(src, 0);
    while (pq.TryDequeue(out char u, out int d)) {
        if (d > dist[u]) continue;
        foreach (var (v, w) in graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.Enqueue(v, dist[v]);
            }
        }
    }
    return dist;
}

Tips

It breaks with negative edge weights. Use Bellman-Ford there.
Stale queue entries are normal. The "d > dist[u]" check skips them.

In the .NET library

PriorityQueue has no "decrease priority" operation, so enqueue the node again with the better distance and skip the stale entry when it surfaces.