Shortest Path Algorithms: Dijkstra and Bellman-Ford

Dijkstra's Algorithm (Directed Weighted Graph, Non-negative)

A greedy approach using a Min-Heap to extract the node with the shortest known distance from the unvisited set and relax its neighbors.

public int[] dijkstra(int n, int[][] edges, int source) {
    // 1. Build adjacency list
    List<int[]>[] adjacency = new List[n];
    for (int i = 0; i < n; i++) adjacency[i] = new ArrayList<>();
    for (int[] e : edges) adjacency[e[0]].add(new int[]{e[1], e[2]});

    // 2. Initialize distances
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // 3. Min-Heap: [cumulativeCost, node]
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, source});

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int cost = top[0], u = top[1];
        
        // Skip if we've already found a better path to u
        if (cost > dist[u]) continue;
        
        for (int[] neighbor : adjacency[u]) {
            int v = neighbor[0], weight = neighbor[1];
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

LeetCode 743 - Network Delay Time

public int networkDelayTime(int[][] times, int n, int k) {
    int[] distances = dijkstra(n + 1, times, k); // Nodes are 1-indexed
    int maxDelay = 0;
    for (int i = 1; i <= n; i++) {
        if (distances[i] == Integer.MAX_VALUE) return -1; // Unreachable node
        maxDelay = Math.max(maxDelay, distances[i]);
    }
    return maxDelay;
}

Bellman-Ford Algorithm (Handles Negative Weights and Cycles)

Relaxes all edges $V-1$ times. If a further relaxation is possible on the $V$-th pass, a negative cycle exists.

public int[] bellmanFord(int n, int[][] edges, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Pass V: Detection of negative cycles
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
            return null; // Negative cycle detected, distances are invalid
        }
    }
    return dist;
}

Floyd-Warshall (All-Pairs Shortest Path)

Computes the shortest path between every pair of nodes. Best for small, dense graphs ($O(V^3)$).

public int[][] floydWarshall(int n, int[][] edges) {
    int[][] matrix = new int[n][n];
    for (int[] row : matrix) Arrays.fill(row, Integer.MAX_VALUE / 2); // Avoid overflow
    for (int i = 0; i < n; i++) matrix[i][i] = 0;
    
    // Fill known edges
    for (int[] e : edges) {
        matrix[e[0]][e[1]] = Math.min(matrix[e[0]][e[1]], e[2]);
    }

    // Tri-nested loop pivot strategy
    for (int k = 0; k < n; k++) { // Intermediate node
        for (int i = 0; i < n; i++) { // Start node
            for (int j = 0; j < n; j++) { // End node
                matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
            }
        }
    }
    return matrix;
}

Summary Selection Table