Dijkstra's Algorithm: Detailed Explanation

Algorithm Overview

Dijkstra's algorithm is a classic algorithm used to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights.

Steps

1. Initialize distances from the source to all nodes as infinity, except the source itself (0).
2. Use a min-priority queue (min-heap) to select the node with the smallest known distance.
3. For each neighbor of the current node, update their distances if a shorter path is found.
4. Repeat until all nodes have been processed.

Time and Memory Complexity

• Time Complexity: O((V + E) log V) using a binary heap
• Space Complexity: O(V + E) for adjacency list and distance tracking

Easy Problems

1. Find shortest path in a small road network

// C++ Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

void dijkstra(int src, vector<pair<int,int>> adj[], vector<int> &dist) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, src});
    dist[src] = 0;
    while (!pq.empty()) {
        int u = pq.top().second, d = pq.top().first;
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

2. Minimum time to deliver a message

Given nodes as communication towers, calculate the fastest time to deliver a message from one tower to another.

Intermediate Problems

1. Network Delay Time (Leetcode 743)

// Assume n nodes, times is edge list
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<pair<int,int>> adj[n+1];
    for (auto &e : times)
        adj[e[0]].push_back({e[1], e[2]});
    vector<int> dist(n+1, 1e9);
    dijkstra(k, adj, dist);
    int res = *max_element(dist.begin()+1, dist.end());
    return res == 1e9 ? -1 : res;
}

2. Cheapest Flights Within K Stops

Use Dijkstra variant with state tracking for number of stops.

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<pair<int,int>> adj[n];
    for (auto &f : flights) adj[f[0]].emplace_back(f[1], f[2]);
    queue<tuple<int,int,int>> q;
    vector<int> cost(n, INT_MAX);
    q.push({src, 0, 0});
    while (!q.empty()) {
        auto [u, c, stops] = q.front(); q.pop();
        if (stops > k) continue;
        for (auto [v, w] : adj[u]) {
            if (c + w < cost[v]) {
                cost[v] = c + w;
                q.push({v, cost[v], stops+1});
            }
        }
    }
    return cost[dst] == INT_MAX ? -1 : cost[dst];
}

Hard Problem

1. Path with Minimum Effort (Leetcode 1631)

Apply Dijkstra with edge weights based on maximum effort.

int minimumEffortPath(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
    pq.push({0, 0, 0});
    dist[0][0] = 0;
    int dir[5] = {-1, 0, 1, 0, -1};
    while (!pq.empty()) {
        auto [d, x, y] = pq.top(); pq.pop();
        if (x == m-1 && y == n-1) return d;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dir[i], ny = y + dir[i+1];
            if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                int nd = max(d, abs(heights[nx][ny] - heights[x][y]));
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    pq.push({nd, nx, ny});
                }
            }
        }
    }
    return 0;
}

All these problems demonstrate the power and flexibility of Dijkstra’s algorithm in handling various pathfinding challenges in graphs.