Dijkstra's Algorithm and BFS for Shortest Path Problems

Shortest path algorithms form the backbone of many graph problems in system design and coding interviews. This guide covers Dijkstra's algorithm for weighted graphs and BFS for unweighted graphs, presenting implementation strategies with clear trade-offs between time complexity, space usage, and practical applicability.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we looking for shortest path in a weighted or unweighted graph?
2. What's the expected size of the input graph (number of nodes and edges)?
3. Can we modify the input graph structure, or must we work with a read-only representation?
4. Should we return just the shortest distance or the actual path?
5. What's the target complexity for follow-ups (e.g., O(V + E) or O(V log V))?

Restatement of the pattern: This is a fundamental graph traversal problem where we need to find the shortest path from a source node to one or more destination nodes in a graph. The pattern can apply to both weighted and unweighted graphs, though the algorithms differ accordingly.

Signal words and constraint shape:

• "Shortest path" or "minimum distance"
• "From A to B" or "from source to all nodes"
• Graph with weighted or unweighted edges
• "Minimum time" or "minimum cost" problems
• Problems that can be modeled as traversing nodes in a graph structure

Assumptions made:

• The graph is connected or we're only concerned with reachable nodes
• We have access to the graph structure (adjacency list or matrix)
• For weighted graphs, all edge weights are non-negative (for Dijkstra's algorithm)
• The problem asks for a single shortest path or all shortest paths from source

Scenario fit: This pattern is best suited for static graph problems where we can precompute or query shortest paths. It's less appropriate for streaming graphs where the structure changes continuously, though variants like incremental Dijkstra can handle some dynamic scenarios.

The pattern is most commonly applied to static graphs where we want to compute shortest paths once and then query efficiently, making it ideal for scenarios like routing in networks, game pathfinding, or optimization problems where we can precompute the optimal route.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Shortest path" or "minimum distance" requirements
• Graph traversal with weighted or unweighted edges
• "Minimum moves" or "least cost" to reach a destination
• Grid-based problems where you can move in 4 directions (up, down, left, right)
• Problems asking for the "minimum time" or "minimum steps" to reach a target

Why this pattern fits better than the most common alternatives:

• BFS is optimal for unweighted graphs or grids where all moves have equal cost, offering O(V + E) time complexity
• Dijkstra's algorithm is better for weighted graphs where edge weights vary, providing O((V + E) log V) complexity
• Compared to DFS, these approaches guarantee finding the optimal path rather than just any path
• Unlike brute force or backtracking, these algorithms systematically explore paths with early termination when optimal solutions are found

Conditions where a variation or related pattern applies instead:

• If the problem has negative edge weights, use Bellman-Ford instead of Dijkstra
• For finding shortest paths between ALL pairs of nodes, use Floyd-Warshall
• If the graph is a DAG (Directed Acyclic Graph), topological sort + dynamic programming might be more efficient
• For problems where you need to find the shortest path with specific constraints (like maximum capacity), specialized algorithms may be needed

The core insight that makes this pattern work: The key insight is that in unweighted graphs or when all edges have equal weight, BFS explores nodes level by level, guaranteeing that the first time we reach a node, we've found the shortest path to it. For weighted graphs, Dijkstra's algorithm uses a priority queue to always expand the node with the smallest known distance, ensuring optimal exploration order. Both algorithms leverage the property that once a node is visited and its distance finalized, we never need to reconsider it.

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force BFS approach because we're looking for the shortest path in an unweighted graph, which should be solvable with simple BFS. But that's O(n²) in the worst case because we might need to explore all nodes and edges multiple times. Let me think about how to optimize this...

I notice that if I maintain a priority queue and always process the node with minimum distance first, I can reduce it to O((V + E) log V) using Dijkstra's algorithm. This is better than BFS alone because we're not just exploring layer by layer, but prioritizing paths that seem more promising.

Actually, let me reconsider - if we're dealing with an unweighted graph, BFS is optimal and simpler. But the problem statement mentions "shortest path basics" which could mean we're looking at weighted graphs or need to handle more complex scenarios.

If the graph is unweighted, BFS is perfect with O(V + E) time complexity. But if it's weighted, we need Dijkstra's algorithm with O((V + E) log V). The key insight is that in weighted graphs, we must explore the shortest distance first to guarantee optimality.

Let me go with Dijkstra's algorithm since it's more general and handles both weighted and unweighted cases efficiently."

Brute-force approach and why it is not ideal:

The most naive approach would be to explore all possible paths from source to destination using DFS or BFS, keeping track of the minimum path length found so far. This approach has exponential time complexity O(k^n) where k is the average branching factor and n is the number of nodes, making it completely impractical for large graphs.

Improved approach and the key optimization:

The key optimization is to use Dijkstra's algorithm with a priority queue (min-heap) to always process the node with the smallest known distance first. This ensures we never revisit nodes with worse distances, and we can terminate early when we reach the destination. The priority queue allows us to maintain the invariant that the next node to process is always the one with minimum distance from source.

Final approach with step-by-step reasoning:

1. Initialize a priority queue with the source node having distance 0
2. Use a distance array to track minimum distances from source to each node
3. Process nodes in order of increasing distance from source
4. For each node, update distances to its neighbors if a shorter path is found
5. Continue until we reach the destination or process all reachable nodes
6. The invariant maintained is that once a node's distance is finalized, it cannot be improved

Important invariants that must hold:

• Distance array always contains the shortest known distance to each node
• Priority queue always maintains nodes sorted by their current shortest distance
• Once a node is removed from the priority queue, its distance is finalized and will not change
• We only explore neighbors of nodes that have been processed (ensuring optimal order)

4. Data Structure Choice

For shortest path problems, the primary data structures needed are:

1. Priority Queue (Min Heap)

• Used in Dijkstra's algorithm to always process the node with minimum distance first
• Essential for maintaining the greedy property of Dijkstra's approach
• Time complexity: O(log V) for insert and extract operations
• Space complexity: O(V) where V is the number of vertices

2. Distance Array/Map

• Stores the shortest known distance from source to each vertex
• Allows quick lookup and update of distances during traversal
• Time complexity: O(1) for access and updates
• Space complexity: O(V)

3. Visited/Processed Set (Optional)

• Tracks which nodes have been processed to avoid reprocessing
• In Dijkstra's case, this is often implicit through distance updates
• Space complexity: O(V)

4. Graph Representation (Adjacency List)

• Most efficient for sparse graphs, which is typical in shortest path problems
• Allows O(1) access to neighbors of any node
• Space complexity: O(V + E) where E is the number of edges

The choice of priority queue as the main data structure is critical - it enables the greedy selection that makes Dijkstra's algorithm optimal. Using a regular queue would make this BFS instead of Dijkstra, which only works for unweighted graphs or when we want to find the minimum number of edges rather than minimum weight.

The adjacency list representation is chosen over matrix representation because:

• It's more space-efficient for sparse graphs
• It allows direct iteration over neighbors without checking all possible edges
• It's the standard way to represent graphs in competitive programming and interviews

A simple HashMap or array can be used for the distance tracking, with the array approach being more efficient for dense graphs or when vertex IDs are sequential.

5. Algorithm Walkthrough

Let me trace through the algorithm using a concrete example to show how it works step by step.

Example: Given a graph with 4 nodes (0,1,2,3) and edges: (0,1,2), (0,2,6), (1,2,3), (1,3,1), (2,3,4). Find shortest path from node 0 to node 3.

Step-by-step execution:

1. Initialization:

   • Distance array: [0, ∞, ∞, ∞]
   • Visited set: {}
   • Priority queue: [(0,0)] - node 0 with distance 0

2. First iteration:

   • Extract node 0 (distance 0)
   • Update neighbors:
     • Node 1: distance 0 + 2 = 2 (smaller than ∞)
     • Node 2: distance 0 + 6 = 6 (smaller than ∞)
   • Distance array: [0, 2, 6, ∞]
   • Priority queue: [(1,2), (2,6)] - node 1 with distance 2, node 2 with distance 6

3. Second iteration:

   • Extract node 1 (distance 2)
   • Update neighbors:
     • Node 2: distance 2 + 3 = 5 (smaller than 6)
     • Node 3: distance 2 + 1 = 3 (smaller than ∞)
   • Distance array: [0, 2, 5, 3]
   • Priority queue: [(3,3), (5,2)] - node 3 with distance 3, node 2 with distance 5

4. Third iteration:

   • Extract node 3 (distance 3)
   • No updates to neighbors since we're at target
   • Distance array: [0, 2, 5, 3]

5. Fourth iteration:

   • Extract node 2 (distance 5)
   • Update neighbors:
     • Node 3: distance 5 + 4 = 9 (not smaller than 3)
   • Distance array remains: [0, 2, 5, 3]

Key invariants maintained throughout:

• Distance[i] represents the shortest known distance from source to node i
• All nodes in priority queue have distances that are valid candidates for shortest path
• Once a node is extracted from queue, its distance is finalized and will not change

Edge case handling:

• If graph has no path to target, the algorithm will return infinity for that node
• If there are negative weights, Dijkstra's won't work correctly (but we're assuming non-negative weights)
• The algorithm handles disconnected components gracefully by not updating unreachable nodes

The algorithm terminates correctly because we process all reachable nodes in order of increasing distance, ensuring that when a node is finalized, we have found its true shortest path.

6. Java Solution

import java.util.*;

public class ShortestPathSolution {
    
    // Dijkstra's algorithm for weighted graph
    public int dijkstra(int[][] edges, int start, int end, int n) {
        // Build adjacency list
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, weight});
            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(new int[]{u, weight});
        }
        
        // Priority queue to get minimum distance node
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        
        distances[start] = 0;
        pq.offer(new int[]{start, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int dist = current[1];
            
            // Skip if we've found a better path already
            if (dist > distances[node]) continue;
            
            // Found the target
            if (node == end) return dist;
            
            // Explore neighbors
            for (int[] neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                int newDist = dist + weight;
                
                if (newDist < distances[nextNode]) {
                    distances[nextNode] = newDist;
                    pq.offer(new int[]{nextNode, newDist});
                }
            }
        }
        
        return -1; // No path found
    }
    
    // BFS for unweighted graph (shortest path in terms of edges)
    public int bfsShortestPath(int[][] edges, int start, int end, int n) {
        // Build adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int[] distances = new int[n];
        Arrays.fill(distances, -1);
        
        queue.offer(start);
        visited.add(start);
        distances[start] = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            
            if (node == end) return distances[node];
            
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    distances[neighbor] = distances[node] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        return -1; // No path found
    }
}

This solution implements both Dijkstra's algorithm for weighted graphs and BFS for unweighted graphs. The key insight is using a priority queue with Dijkstra to always process the node with minimum distance first, while BFS naturally explores nodes in order of their distance from source. Both approaches maintain necessary invariants to ensure correctness and optimal performance.

7. Complexity Analysis

Time Complexity: O((V + E) log V) where V is the number of vertices and E is the number of edges.

The algorithm uses a priority queue (min-heap) to always process the vertex with minimum distance. Each vertex is inserted into the priority queue at most once, and each edge is processed once. The heap operations (insert and extract-min) take O(log V) time, leading to the overall complexity.

Space Complexity: O(V) for storing distances, visited flags, and the priority queue.

The space usage is dominated by:

• Distance array: O(V)
• Visited boolean array: O(V)
• Priority queue: O(V) in worst case (all vertices in queue simultaneously)

Why these bounds are correct:

• Each vertex is processed exactly once, so the outer loop runs V times
• Each edge is examined once during relaxation, contributing O(E) work overall
• The priority queue operations are amortized O(log V) per vertex, giving us the log factor
• The total work is bounded by the number of vertices and edges in the graph

Optimality: This complexity is optimal for the general weighted directed graph shortest path problem when using Dijkstra's algorithm with a binary heap. For unweighted graphs, BFS provides O(V + E) optimal complexity, but Dijkstra's is the standard choice when edge weights are non-negative. The O((V + E) log V) bound matches the theoretical lower bound for this class of problems with the given constraints.

The solution is near-optimal for weighted graphs with non-negative edge weights, as any comparison-based algorithm must examine each edge at least once to ensure correctness.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty graph: When n = 0 or no edges exist, the solution should return appropriate default values (e.g., Integer.MAX_VALUE for unreachable nodes)
• Single node: When n = 1, all distances should be 0, and there are no edges to process
• No path exists: When the destination is unreachable from source, return Integer.MAX_VALUE or handle appropriately

Duplicate Values and Repeated States

• Duplicate edges: Multiple edges between same nodes should be handled by taking the minimum weight (if using weighted graph)
• Repeated relaxations: In Dijkstra's algorithm, same node can be processed multiple times; the priority queue ensures we process the shortest path first
• Negative weights: While Dijkstra handles non-negative weights, negative edges can cause incorrect results; use Bellman-Ford for such cases

Boundary Conditions

• Source equals destination: Distance should be 0, no traversal needed
• All nodes are connected: When every node is reachable from every other node, the algorithm should find optimal paths
• Large input sizes: With up to 10^4 nodes, ensure O((V + E) log V) complexity is maintained with proper data structures

Common Implementation Mistakes

• Not handling visited nodes properly: In BFS, a node might be added to queue multiple times; use a visited set to avoid reprocessing
• Incorrect distance updates: Only update distance if new path is shorter than existing one (for Dijkstra)
• Wrong priority queue usage: In Dijkstra, use PriorityQueue with custom comparator for distance; failing to do so leads to wrong order of processing
• Missing edge case in graph representation: When using adjacency lists, ensure all nodes are properly initialized even if they have no outgoing edges

// Example edge case handling:
if (source == destination) return 0;
if (graph.isEmpty() || !graph.containsKey(source)) return Integer.MAX_VALUE;

Memory vs Performance Trade-offs

• Visited set vs distance array: Using a visited set prevents reprocessing but requires additional space; using distance array with proper comparison can be more memory-efficient
• Graph representation: Adjacency list vs matrix affects both space and time complexity; adjacency list preferred for sparse graphs

9. Alternative Approaches

There are several alternative approaches to solving shortest path problems, each with their own trade-offs:

Floyd-Warshall Algorithm: This approach computes shortest paths between all pairs of vertices in O(V³) time. It's suitable when you need the shortest distances between every pair of nodes, but it's inefficient for sparse graphs or when only a single source-target path is needed. The space complexity is O(V²) for storing the distance matrix.

Bellman-Ford Algorithm: This handles negative edge weights and can detect negative cycles, making it more versatile than Dijkstra's algorithm. It runs in O(VE) time but is slower than Dijkstra for graphs without negative edges. Bellman-Ford is useful when the input graph might contain negative weight edges.

A Algorithm*: When you have a heuristic function that estimates the distance from any node to the target, A* can be significantly faster than Dijkstra in practice. It's particularly effective for grid-based pathfinding problems like navigation or game AI, but requires a good heuristic to maintain optimality.

BFS for Unweighted Graphs: For graphs where all edges have equal weight (typically 1), BFS is optimal and simpler than Dijkstra's algorithm. It runs in O(V + E) time and uses less memory since it only needs a queue, not a priority queue.

The chosen solution (Dijkstra with priority queue) is optimal for weighted graphs with non-negative edge weights, offering O((V + E) log V) time complexity and is preferred over alternatives when the problem constraints match this pattern.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic graph with multiple paths
        // Graph: 0-1(2), 0-2(1), 1-2(3), 1-3(1), 2-3(4)
        // Expected: shortest distance from 0 to 3 is 3
        int[][] edges1 = {{0,1,2}, {0,2,1}, {1,2,3}, {1,3,1}, {2,3,4}};
        int n1 = 4;
        int start1 = 0;
        int end1 = 3;
        // Expected result: 3
        
        // Test Case 2: Single node graph
        int[][] edges2 = {};
        int n2 = 1;
        int start2 = 0;
        int end2 = 0;
        // Expected result: 0
        
        // Test Case 3: Disconnected graph
        int[][] edges3 = {{0,1,2}, {2,3,1}};
        int n3 = 4;
        int start3 = 0;
        int end3 = 3;
        // Expected result: Integer.MAX_VALUE (no path exists)
        
        // Test Case 4: Graph with negative edge weights (should fail with Dijkstra)
        int[][] edges4 = {{0,1,-1}, {1,2,1}};
        int n4 = 3;
        int start4 = 0;
        int end4 = 2;
        // Expected result: -1 (or handle appropriately)
        
        // Test Case 5: Path with zero weight edges
        int[][] edges5 = {{0,1,0}, {1,2,2}, {0,2,1}};
        int n5 = 3;
        int start5 = 0;
        int end5 = 2;
        // Expected result: 1
    }
}

Sample Test Cases:

Basic Path Example:

• Input: edges = [[0,1,2], [0,2,1], [1,2,3], [1,3,1], [2,3,4]], n = 4, start = 0, end = 3
• Expected: 3 (path: 0→2→3 with weight 1+4=5, or 0→1→3 with weight 2+1=3)

Single Node:

• Input: edges = [], n = 1, start = 0, end = 0
• Expected: 0

Disconnected Components:

• Input: edges = [[0,1,2], [2,3,1]], n = 4, start = 0, end = 3
• Expected: Integer.MAX_VALUE (no path exists)

Zero Weight Edges:

• Input: edges = [[0,1,0], [1,2,2], [0,2,1]], n = 3, start = 0, end = 2
• Expected: 1 (direct path is better than 0→1→2)

Edge Case - No Path:

• Input: edges = [[0,1,2]], n = 3, start = 0, end = 2
• Expected: Integer.MAX_VALUE (no path exists)

11. Final Summary

The core idea is to use a priority queue-based Dijkstra's algorithm to efficiently find the shortest path in weighted graphs by always expanding the node with the minimum accumulated cost first. This solution works optimally for graphs with non-negative edge weights, leveraging the greedy property that once a node is visited, its shortest distance is finalized. The efficiency comes from avoiding redundant path exploration through the priority queue's heap property, making it significantly faster than brute force approaches that would examine all possible paths. The solution is optimal for the given constraints and handles the essential graph traversal requirements with clean, maintainable code structure.