Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall, A*)

Shortest Path Algorithms Matrix

Dijkstra: Single-source shortest path for non-negative edge weights using Priority Queue. Time: $O((V+E) \log V)$.

Production Code Example:

import java.util.*;
public class DijkstraDemo {
    static class Edge { int to, weight; Edge(int t, int w) { to = t; weight = w; } }
    public int[] dijkstra(int n, List<List<Edge>> adj, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (d > dist[u]) continue;
            for (Edge e : adj.get(u)) {
                if (dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                    pq.offer(new int[]{e.to, dist[e.to]});
                }
            }
        }
        return dist;
    }
}

Key Complexity & Algorithmic Takeaways:

When implementing Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall, A*) in coding interviews and production applications, keep these core guidelines in mind:

• Time Complexity Analysis: Always evaluate best-case, average-case, and worst-case time complexities ($O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$).
• Space Complexity & Memory Bounds: Account for auxiliary memory usage, call stack frame recursion overhead, and heap allocations.
• Edge Cases & Validation: Test empty inputs, null pointers, single-element collections, duplicate values, and integer overflow bounds.
• Optimal vs Naive Solutions: Start with a clear brute-force solution, then optimize using techniques like Hashing, Two Pointers, Windowing, or Dynamic Programming.

Summary Takeaway:

Mastering Shortest Path (Dijkstra, Bellman-Ford, Floyd-Warshall, A*) provides the foundational problem-solving skills needed to pass technical coding interviews at top tech companies and write ultra-performant software systems.