Dijkstra

Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

It's a greedy BFS algorithm.

It does NOT support negative edge.

Note that we should only use this algorithm on a weighted graph. If it's an unweighted graph, just use BFS.

Algorithm

Summary: Use heap to store the cost of nodes. Each time pop the heap top node, whose shortest path is determimed once popped, and use its outbound edges to relax its neighbors and push the relaxed neighbors into the heap.

Given V vertices and E edges. The all weights of all edges are non-negative. Find the smallest distance from a source node S to all other nodes.

We split the V vertices into two sets:

• A, visited nodes, i.e. those whose shortest path is already determined.

• B, unvisited nodes.

Initially:

• A is empty and B contains all the vertices

• The distance of the source vertex is 0, and Infinity for all other vertices.

Then we keep the following operations until all vertices are visited:

1. Find the vertice with the smallest distance from B, say u. Move u from B to A.

2. For each outbound edge from u (u, v, w) (v is the destination verte, w is the weight), try to relax v using u and w -- If dist[v] > dist[u] + w, then dist[v] = dist[u] + w.

Why no negative edge?

Dijkstra is a greedy algorithm. If all the edges are non-negative, once we find the node with the smallest cost from unvisited vertice set, say u, we are sure that it won't be updated later -- it's already the optimal path.

But if there are negative edges, this u can be updated again later using negative edge.

Implementation

Here I only talk about the solution using priority_queue.

Let pq be a priority_queue of pairs of the cost (i.e. the length of the shortest path from src) and the vertex index. The element with the smallest cost is at the top of the queue (i.e. min-heap). Initially pq only has (0, src) in it.

Let dist[u] be the cost of u. Initially dist[src] = 0 and dist[u] = INF for all other vertices.

// Time: O(ElogE)
// Space: O(E)
typedef unordered_map<int, unordered_map<int, int>> Graph; // map from source node to <destination node, edge cost>
typedef pair<int, int> iPair;
vector<int> dijkstra(Graph &graph, int N, int source) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq; // cost, nodeIndex. Min-heap -- the unvisited ndoe with the smallest distance is at the top
    vector<int> dists(N, INT_MAX), seen(N);
    dists[source] = 0;
    pq.emplace(0, source); // push the source node into heap
    while (pq.size()) {
        int u = pq.top().second; // greedily visit the unvisited node with smallest cost, and relax its neighbors
        pq.pop();
        if (seen[u]) continue; // `u` has been visited, skip
        seen[u] = 1; // mark `u` as visited
        for (auto &neighbor : graph[u]) { // try to use node `u` to relax its neighbors
            int v = neighbor.first, weight = neighbor.second;
            if (!seen[u] && dists[v] > dists[u] + weight) { // If `v` is not visited and can be relaxed
                dists[v] = dists[u] + weight; // update the cost
                pq.emplace(dists[v], v); // push the updated pair of <cost, index> into the heap
            }
        }
    }
    return dists;
}

When the same node has been relaxed multiple times, we should delete the old relaxations from the priority queue. But with priority_queue, we don't have a way to do it. So we just push the entry of the same node and smaller cost into the priority queue.

When a node is popped from the queue and it's already visited, then we should skip it.

Time complexity analysis: In the worst case, each visited node will push new items into the priority queue using all its outbound edges. So there will be O(E) items in the priority queue in total. The overall time complexity is Elog(E).

If we can use Fabonacci Heap, the time complexity will be reduced to O(E + VlogV).

Another way to prevent visiting the same node twice is as follows:

// Time: O(ElogE)
// Space: O(E)
typedef unordered_map<int, unordered_map<int, int>> Graph;
typedef pair<int, int> PII;
vector<int> dijkstra(Graph &graph, int N, int source) {
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    vector<int> dists(N, INT_MAX);
    dists[source] = 0;
    pq.emplace(0, source);
    while (pq.size()) {
        const [cost, u] = pq.top();
        pq.pop();
        if (cost > dists[u]) continue; // this is already not the optimal, skip
        for (auto &[v, w] : graph[u]) {
            if (dists[v] > dists[u] + w) {
                dists[v] = dists[u] + w;
                pq.emplace(dists[v], v);
            }
        }
    }
    return dists;
}

Problems

• 743. Network Delay Time

• 787. Cheapest Flights Within K Stops

• 1514. Path with Maximum Probability (Medium)

• 1368. Minimum Cost to Make at Least One Valid Path in a Grid (Hard)

Reference

• Dijkstra's algorithm