Shortest Path Algorithms

Algorithm	Time	Space	Use Case
BFS	O(V + E)	O(V)	Unweighted graph
Dijkstra	O((V + E) log V)	O(V)	Single source, non-negative
Bellman-Ford	O(V × E)	O(V)	Negative edges, cycle detection
Floyd-Warshall	O(V³)	O(V²)	All pairs shortest path
0-1 BFS	O(V + E)	O(V)	Weights 0 or 1 only

02

Dijkstra's Algorithm

Dijkstra's algorithm is the workhorse of shortest path algorithms. Invented by Edsger Dijkstra in 1956, it remains the most efficient solution for graphs with non-negative edge weights - which covers most real-world scenarios.

Understanding Dijkstra's Algorithm

Think of Dijkstra's algorithm like ripples spreading from a stone dropped in water. Starting from the source, we expand outward, always processing the closest unvisited node first. This greedy approach works because once we've found the shortest path to a node, we know it can't be improved (assuming no negative edges).

Greedy Algorithm

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a Priority Queue (min-heap) to always select the vertex with the smallest known distance, then "relaxes" all its outgoing edges.

Relaxation is the core operation: for each neighbor, check if going through the current vertex provides a shorter path. If dist[current] + weight < dist[neighbor], update the neighbor's distance and add it to the priority queue. This process continues until all reachable vertices are processed.

Key properties: Time complexity O((V+E) log V) with a binary heap, greedy (processes closest first), produces a shortest path tree, fails with negative edges because it assumes processed nodes are finalized.

Why does Dijkstra fail with negative edges? The greedy assumption is that once we pop a vertex from the priority queue, we've found its shortest path. But a negative edge later could provide an even shorter path! That's why we need Bellman-Ford for graphs with negative weights.

O((V+E) log V)

int[] dijkstra(int n, List> adj, int source) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    
    // Min-heap: {distance, node}
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, source});
}

Distance Array

All nodes start at ∞ except source = 0

Priority Queue

Min-heap sorted by distance. Stores {dist, node}

Start Point

Add source to PQ with distance 0

Greedy Choice

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        
        // Skip if we already found a shorter path
        if (d > dist[u]) continue;

Poll Minimum

Always process the node with smallest distance first. This greedy choice is what makes Dijkstra work!

Skip Outdated

If polled distance > known distance, we already found a better path. Skip to avoid redundant work.

Core Logic

        // Relaxation - try to improve neighbor distances
        for (int[] edge : adj.get(u)) {
            int v = edge[0], weight = edge[1];
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

Relaxation Formula

If dist[u] + weight < dist[v], we found a shorter path to v through u. Update it!

Add to Queue

Push updated distance to PQ. Lazy deletion - old entries will be skipped when polled.

Key Insight: We may add the same node multiple times with different distances. That's okay! The skip check (if (d > dist[u]) continue) ensures we only process each node once with its optimal distance.

Adjacency List

List> buildGraph(int n, int[][] edges) {
    List> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        adj.get(u).add(new int[]{v, w});
        adj.get(v).add(new int[]{u, w});  // For undirected
    }
    return adj;
}

Weighted adjacency list stores {neighbor, weight} pairs. For undirected graphs, add edges in both directions. Remove the second add() for directed graphs.

Find Actual Path

List dijkstraWithPath(int n, List> adj, int src, int dest) {
    int[] dist = new int[n];
    int[] parent = new int[n];  // Track path
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);
    dist[src] = 0;
    
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        
        if (u == dest) break;  // Early exit optimization
        if (d > dist[u]) continue;
        
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;  // Remember where we came from
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    
    // Reconstruct path by backtracking
    List path = new ArrayList<>();
    for (int at = dest; at != -1; at = parent[at]) {
        path.add(at);
    }
    Collections.reverse(path);
    return path;
}

Parent Array

Store where each node came from during relaxation

Early Exit

Stop when destination is popped (guaranteed shortest)

Backtrack

Follow parent pointers from dest → src, then reverse

Dijkstra's Step-by-Step Example

Weighted Graph

Initial State

dist[A] = 0 dist[B] = ∞ dist[C] = ∞ dist[D] = ∞

Source A starts with distance 0, all others infinity

Step 1

Process A (dist=0)

Update: B=2, C=1

Step 2

Process C (dist=1)

B = min(2, 1+4) = 2 (no change)

Step 3

Process B (dist=2)

Update: D=2+3=5

Step 4

Process D (dist=5)

No more updates needed

Final Distances

A = 0 B = 2 C = 1 D = 5

Priority Queue Flow

[(0,A)] → [(1,C),(2,B)] → [(2,B),(5,D)] → [(5,D)] → []

Practice Questions: Dijkstra's Algorithm

Given:

Graph (node -> [(neighbor, weight)]):
0 -> [(1, 4), (2, 1)]
1 -> [(3, 1)]
2 -> [(1, 2), (3, 5)]
3 -> []

Source: 0

Task: Find shortest distances from node 0 to all other nodes. Show the PriorityQueue state after each step.

Expected output: dist[] = {0, 3, 1, 4}

Show Solution

// Initial: dist = [0, INF, INF, INF], PQ = [(0, 0)]

// Process node 0 (dist=0):
//   Update node 1: dist[1] = 0 + 4 = 4
//   Update node 2: dist[2] = 0 + 1 = 1
//   dist = [0, 4, 1, INF], PQ = [(1, 2), (4, 1)]

// Process node 2 (dist=1):
//   Update node 1: dist[1] = min(4, 1+2) = 3
//   Update node 3: dist[3] = 1 + 5 = 6
//   dist = [0, 3, 1, 6], PQ = [(3, 1), (4, 1), (6, 3)]

// Process node 1 (dist=3):
//   Update node 3: dist[3] = min(6, 3+1) = 4
//   dist = [0, 3, 1, 4]

// Final: dist = [0, 3, 1, 4]
// Shortest path to 3: 0 -> 2 -> 1 -> 3 (cost = 4)

Given:

// Weighted graph edges: [from, to, weight]
int[][] edges = {{0,1,2}, {0,2,4}, {1,2,1}, {1,3,7}, {2,3,3}};
int source = 0, target = 3;

Task: Find the shortest path from 0 to 3 and return the actual path (not just the distance).

Expected output: Path = [0, 1, 2, 3], Distance = 6

Show Solution

int[] dijkstraWithPath(int n, int[][] edges, int src, int target) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(new int[]{e[1], e[2]});
        graph.get(e[1]).add(new int[]{e[0], e[2]}); // undirected
    }
    
    int[] dist = new int[n], parent = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);
    dist[src] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
    pq.offer(new int[]{0, src});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;
        
        for (int[] neighbor : graph.get(u)) {
            int v = neighbor[0], w = neighbor[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;  // Track path
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    
    // Reconstruct path
    List<Integer> path = new ArrayList<>();
    for (int node = target; node != -1; node = parent[node]) {
        path.add(0, node);
    }
    // path = [0, 1, 2, 3], dist[3] = 6
}

Problem: You have a network of n nodes. Given times where times[i] = [u, v, w] represents a signal traveling from u to v with time w. Return the minimum time for all nodes to receive signal from node k, or -1 if impossible.

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Expected output: 2

Show Solution

public int networkDelayTime(int[][] times, int n, int k) {
    // Build adjacency list
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>())
             .add(new int[]{t[1], t[2]});
    }
    
    // Dijkstra
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
    pq.offer(new int[]{0, k});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;
        
        if (graph.containsKey(u)) {
            for (int[] next : graph.get(u)) {
                int v = next[0], w = next[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
    }
    
    // Find max delay (all nodes must receive signal)
    int maxDelay = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        maxDelay = Math.max(maxDelay, dist[i]);
    }
    return maxDelay;  // 2
}

03

Bellman-Ford Algorithm

When edges can have negative weights, Dijkstra's greedy approach breaks down. Bellman-Ford uses a more methodical approach - relaxing all edges repeatedly until no improvements can be made.

Understanding Bellman-Ford

Unlike Dijkstra's greedy approach, Bellman-Ford takes a "brute force" strategy: it relaxes every single edge in the graph, and repeats this process V-1 times. This guarantees that shortest paths propagate correctly even when negative edges create non-intuitive shortcuts. The tradeoff? It's slower: O(V × E) vs Dijkstra's O((V+E) log V).

Dynamic Programming

Bellman-Ford Algorithm

The Bellman-Ford algorithm finds shortest paths from a single source vertex to all other vertices, even when the graph contains negative edge weights. It works by repeatedly relaxing all edges V-1 times, where V is the number of vertices.

Why V-1 iterations? The longest possible shortest path in a graph with V vertices contains at most V-1 edges (visiting each vertex once). Each iteration guarantees at least one more vertex gets its correct shortest path distance. After V-1 iterations, all shortest paths are found.

Negative cycle detection: After V-1 iterations, run one more pass. If any distance can still be reduced, the graph contains a negative cycle - a loop where the total weight is negative. In such graphs, shortest paths are undefined (you could loop infinitely to decrease cost).

Key properties: Time O(V × E), handles negative weights, detects negative cycles, uses edge list representation, simpler to implement than Dijkstra but slower on dense graphs.

Common Interview Use Cases: Currency arbitrage detection (negative cycles = profit loops), network routing with variable costs, and any graph problem that explicitly mentions "negative weights".

O(V × E)

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

Distance Array

All nodes start at Integer.MAX_VALUE (infinity) except the source which starts at 0. This represents "unreachable" initially.

Edge List Format

Unlike Dijkstra, Bellman-Ford uses an edge list (array of edges) instead of adjacency list. Each edge is {u, v, weight}.

Core Algorithm

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

Why V-1 Times?

The longest possible shortest path has V-1 edges (visiting all V vertices). Each iteration guarantees at least one more vertex gets its correct distance.

Relaxation

If going through u to reach v is shorter than current dist[v], update it. Same formula as Dijkstra: dist[u] + w < dist[v]

Overflow Guard

Check dist[u] != MAX_VALUE first to avoid integer overflow when adding weight to infinity.

Key Difference from Dijkstra: Bellman-Ford relaxes ALL edges in every iteration (brute force), while Dijkstra smartly picks the minimum distance node first. This brute force approach is slower but handles negative edges correctly!

Negative Cycle Check

    // Check for negative cycle (V-th iteration)
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        
        if (dist[u] != Integer.MAX_VALUE && 
            dist[u] + w < dist[v]) {
            // Negative cycle detected!
            return null;
        }
    }
    
    return dist;
}

Why One More Iteration?

After V-1 iterations, all shortest paths are finalized IF no negative cycle exists. If the V-th iteration still improves any distance, we can keep improving forever → negative cycle!

What is a Negative Cycle?

A cycle where the sum of edge weights is negative. You can loop forever and keep reducing the "shortest" path to negative infinity. No valid shortest path exists!

Alternative Version

boolean hasNegativeCycle(int n, int[][] edges) {
    int[] dist = new int[n];
    // Start with all zeros (no source needed for cycle detection)
    
    // V-1 relaxation iterations
    for (int i = 0; i < n - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // V-th iteration - if anything changes, cycle exists
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] + w < dist[v]) {
            return true;  // Negative cycle found!
        }
    }
    
    return false;
}

When to Use This

Use this version when you only care about detecting if a negative cycle exists anywhere in the graph, not finding shortest paths from a specific source.

Simplified Logic

No overflow check needed since we start with zeros. Returns simple boolean instead of distance array. Common in "detect arbitrage" or "currency exchange" problems.

BFS vs Dijkstra vs Bellman-Ford

BFS

Data Structure:

Queue (FIFO)

Edge Weights:

Unweighted (=1)

Relaxation:

Visit once

Dijkstra

Data Structure:

Priority Queue (Min-Heap)

Edge Weights:

Non-negative

Relaxation:

Process min first

Bellman-Ford

Data Structure:

Edge List

Edge Weights:

Any (including negative)

Relaxation:

Relax all edges V-1 times

When Dijkstra Fails (Negative Edge)

Dijkstra's Problem

Picks B first (dist=5) and never revisits it!

Dijkstra says: B = 5

Bellman-Ford Solution

Iteration 3: B = min(5, 2-4) = -2 ✓

Path: A → C → B is cheaper!

Practice Questions: Bellman-Ford Algorithm

Given:

Edges: [[0,1,4], [0,2,2], [1,2,-3], [2,3,2]]
(format: [from, to, weight])
Number of nodes: 4, Source: 0

Task: Find shortest distances from node 0 to all nodes using Bellman-Ford.

Expected output: dist[] = {0, 4, 1, 3}

Show Solution

// Run V-1 = 3 iterations
// Initial: dist = [0, INF, INF, INF]

// Iteration 1:
//   Edge 0->1: dist[1] = 0 + 4 = 4
//   Edge 0->2: dist[2] = 0 + 2 = 2
//   Edge 1->2: dist[2] = min(2, 4-3) = 1
//   Edge 2->3: dist[3] = 1 + 2 = 3
//   dist = [0, 4, 1, 3]

// Iteration 2: No changes (already optimal)
// Iteration 3: No changes

// Final: dist = [0, 4, 1, 3]
// Path to node 2: 0 -> 1 -> 2 (cost = 4-3 = 1)

Given:

Edges: [[0,1,1], [1,2,-1], [2,0,-1]]
Number of nodes: 3

Task: Determine if the graph contains a negative cycle. Explain your reasoning.

Expected output: true (negative cycle exists)

Show Solution

// Run V-1 = 2 iterations first
// Initial: dist = [0, INF, INF]

// Iteration 1:
//   Edge 0->1: dist[1] = 0 + 1 = 1
//   Edge 1->2: dist[2] = 1 + (-1) = 0
//   Edge 2->0: dist[0] = min(0, 0-1) = -1
//   dist = [-1, 1, 0]

// Iteration 2:
//   All edges can still improve! This continues forever.

// V-th iteration (cycle detection):
//   Edge 0->1: -1 + 1 = 0 < 1 -- STILL UPDATING!
//   
// Cycle: 0 -> 1 -> 2 -> 0
// Cycle weight: 1 + (-1) + (-1) = -1 (NEGATIVE!)

boolean hasNegativeCycle(int n, int[][] edges) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;
    
    // V-1 relaxations
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            if (dist[e[0]] != Integer.MAX_VALUE &&
                dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
            }
        }
    }
    
    // V-th check for negative cycle
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE &&
            dist[e[0]] + e[2] < dist[e[1]]) {
            return true;  // Negative cycle detected!
        }
    }
    return false;
}

Problem: Find the cheapest price from src to dst with at most k stops. Return -1 if no such route exists.

n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0, dst = 3, k = 1

Expected output: 700 (path: 0 -> 1 -> 3)

Show Solution

public int findCheapestPrice(int n, int[][] flights, 
                             int src, int dst, int k) {
    // Modified Bellman-Ford: run exactly k+1 iterations
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    
    // k stops = k+1 edges
    for (int i = 0; i <= k; i++) {
        // IMPORTANT: Use copy to avoid using updates from same iteration
        int[] temp = dist.clone();
        
        for (int[] f : flights) {
            int from = f[0], to = f[1], price = f[2];
            if (dist[from] != Integer.MAX_VALUE) {
                temp[to] = Math.min(temp[to], dist[from] + price);
            }
        }
        dist = temp;
    }
    
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

// Trace for k=1 (2 iterations):
// Initial: dist = [0, INF, INF, INF]

// Iteration 1 (1 edge):
//   0->1: temp[1] = 100
//   temp = [0, 100, INF, INF]

// Iteration 2 (2 edges / 1 stop):
//   1->2: temp[2] = 200
//   1->3: temp[3] = 700
//   2->3: can't use (would be 2 stops)
//   temp = [0, 100, 200, 700]

// Answer: 700 (0 -> 1 -> 3)

04

Floyd-Warshall Algorithm

What if you need shortest paths between every pair of vertices? Running Dijkstra V times works, but Floyd-Warshall offers a beautifully simple alternative using dynamic programming.

Understanding Floyd-Warshall

Floyd-Warshall asks a clever question: "Can we improve the path from i to j by going through an intermediate vertex k?" It systematically tries every possible intermediate vertex, building up shortest paths from simpler subproblems. The result is an elegant triple-nested loop that computes all-pairs shortest paths.

Dynamic Programming

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices in a weighted graph. It uses a 2D distance matrix where dist[i][j] represents the shortest known path from vertex i to vertex j.

The DP recurrence: For each possible intermediate vertex k, check if routing through k improves the path: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). The key insight is that after considering vertices 0 through k as intermediates, we have optimal paths using only those vertices.

Negative cycle detection: After the algorithm completes, check the diagonal. If any dist[i][i] < 0, there's a negative cycle passing through vertex i. The graph's shortest paths are then undefined.

Key properties: Time O(V³), Space O(V²), handles negative edges, detects negative cycles, beautifully simple code (just 3 nested loops), best when you need ALL pairs of shortest paths.

When to use Floyd-Warshall vs running Dijkstra V times? Floyd-Warshall is O(V³) regardless of edge count. Running Dijkstra V times is O(V(V+E) log V). For dense graphs (many edges), Floyd-Warshall is often simpler and competitive. For sparse graphs, repeated Dijkstra may be faster.

O(V³) Time | O(V²) Space

int[][] floydWarshall(int n, int[][] edges) {
    int INF = Integer.MAX_VALUE / 2;  // Avoid overflow
    int[][] dist = new int[n][n];
    
    // Initialize distance matrix
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
        dist[i][i] = 0;  // Distance to self is 0
    }
    
    // Add edge weights
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        dist[u][v] = w;
        // dist[v][u] = w;  // Uncomment for undirected
    }
}

2D Distance Matrix

dist[i][j] = shortest path from i to j. Initially set to edge weight or infinity if no direct edge.

Why MAX_VALUE / 2?

Prevents integer overflow when adding two "infinity" values. INF + INF would overflow with MAX_VALUE!

Self-Distance = 0

Distance from any node to itself is always 0. This is set on the diagonal: dist[i][i] = 0

Core DP Logic

    // DP: Try each vertex k as intermediate node
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

The Key Insight

For every pair (i, j), ask: "Is it shorter to go through vertex k?" If i→k→j < i→j, update!

Loop Order Matters!

k must be the outer loop! We need all paths using vertices {0..k-1} computed before considering k as intermediate.

DP State Transition

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) - classic DP relaxation

Why It Works: After iteration k, dist[i][j] contains the shortest path from i to j using only vertices {0, 1, ..., k} as intermediate nodes. After all n iterations, we've considered ALL possible intermediate vertices!

Negative Cycle Check

    // Check for negative cycle
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            // Negative cycle detected!
            return null;
        }
    }
    
    return dist;
}

Why Check Diagonal?

If dist[i][i] < 0, there's a path from i back to i with negative total weight. That's a negative cycle reachable from i!

What Does It Mean?

A negative cycle means you can keep looping to reduce distance infinitely. No valid shortest path exists for nodes in or reachable from the cycle.

Path Reconstruction

int[][] next;  // next[i][j] = next node on path from i to j

void floydWithPath(int n, int[][] edges) {
    int INF = Integer.MAX_VALUE / 2;
    int[][] dist = new int[n][n];
    next = new int[n][n];
    
    // Initialize
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
        Arrays.fill(next[i], -1);
        dist[i][i] = 0;
    }
    
    // Add edges - also set next pointer
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        dist[u][v] = w;
        next[u][v] = v;  // From u, go directly to v
    }
    
    // DP with path tracking
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];  // Go toward k first
                }
            }
        }
    }
}

Next Array

next[i][j] stores the first step on the shortest path from i to j. When we update via k, we redirect: next[i][j] = next[i][k]

Why next[i][k]?

If the best path from i→j goes through k, the first step is the same as the first step from i→k. We already know that from next[i][k]!

Retrieve Path

List getPath(int u, int v) {
    if (next[u][v] == -1) return Collections.emptyList();
    
    List path = new ArrayList<>();
    path.add(u);
    while (u != v) {
        u = next[u][v];  // Follow the trail
        path.add(u);
    }
    return path;
}

Follow the next pointers like a linked list! Start at u, keep jumping to next[current][v] until you reach v. Each step brings you closer to the destination on the shortest path. Returns empty list if no path exists (next[u][v] == -1).

Practice Questions: Floyd-Warshall Algorithm

Given:

Initial distance matrix:
     0   1   2
0 [  0,  3,  8 ]
1 [INF,  0,  1 ]
2 [  4, INF, 0 ]

Task: Complete the all-pairs shortest path matrix using Floyd-Warshall. Show the matrix after each k iteration.

Show Solution

// k = 0 (through vertex 0):
// dist[1][2] = min(1, dist[1][0]+dist[0][2]) = min(1, INF+8) = 1
// dist[2][1] = min(INF, dist[2][0]+dist[0][1]) = min(INF, 4+3) = 7
// Matrix after k=0:
//   [0, 3, 8]
//   [INF, 0, 1]
//   [4, 7, 0]

// k = 1 (through vertex 1):
// dist[0][2] = min(8, dist[0][1]+dist[1][2]) = min(8, 3+1) = 4
// dist[2][0] = min(4, dist[2][1]+dist[1][0]) = min(4, 7+INF) = 4
// Matrix after k=1:
//   [0, 3, 4]
//   [INF, 0, 1]
//   [4, 7, 0]

// k = 2 (through vertex 2):
// dist[0][1] = min(3, dist[0][2]+dist[2][1]) = min(3, 4+7) = 3
// dist[1][0] = min(INF, dist[1][2]+dist[2][0]) = min(INF, 1+4) = 5
// Final matrix:
//   [0, 3, 4]
//   [5, 0, 1]
//   [4, 7, 0]

Problem: After running Floyd-Warshall, determine if the graph is strongly connected (every vertex can reach every other vertex).

Final distance matrix:
     0   1   2   3
0 [  0,  2,  4,  7 ]
1 [INF,  0,  2,  5 ]
2 [INF, INF, 0,  3 ]
3 [INF, INF, INF, 0]

Task: Is this graph strongly connected? Why or why not?

Show Solution

// A graph is strongly connected if dist[i][j] != INF
// for ALL pairs (i, j).

// Checking the matrix:
// dist[1][0] = INF -- Node 1 cannot reach node 0!
// dist[2][0] = INF -- Node 2 cannot reach node 0!
// dist[2][1] = INF -- Node 2 cannot reach node 1!
// dist[3][0] = INF, dist[3][1] = INF, dist[3][2] = INF

// Answer: NO, the graph is NOT strongly connected.
// This appears to be a DAG (directed acyclic graph)
// with edges only going from lower to higher indices.

boolean isStronglyConnected(int[][] dist, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == Integer.MAX_VALUE) {
                return false;
            }
        }
    }
    return true;
}

Problem: Given n cities and weighted edges, find the city with the smallest number of cities reachable through paths of distance at most distanceThreshold. If there's a tie, return the city with the greatest number.

n = 4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
distanceThreshold = 4

Expected output: 3

Show Solution

public int findTheCity(int n, int[][] edges, int threshold) {
    int[][] dist = new int[n][n];
    int INF = (int) 1e9;
    
    // Initialize
    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) {
        dist[e[0]][e[1]] = e[2];
        dist[e[1]][e[0]] = e[2];  // undirected
    }
    
    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // Count reachable cities within threshold
    int result = 0, minCount = n;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (i != j && dist[i][j] <= threshold) {
                count++;
            }
        }
        // <= because we want greatest index on tie
        if (count <= minCount) {
            minCount = count;
            result = i;
        }
    }
    return result;  // City 3
}

// After Floyd-Warshall:
// City 0: can reach 1,2,3 within dist 4 -> count=3
// City 1: can reach 0,2,3 within dist 4 -> count=3
// City 2: can reach 1,3 within dist 4 -> count=2
// City 3: can reach 2 within dist 4 -> count=1 (smallest!)
// Answer: 3

05

0-1 BFS

When all edge weights are either 0 or 1, we can do better than Dijkstra! 0-1 BFS achieves O(V + E) time by using a clever deque-based approach instead of a priority queue.

Understanding 0-1 BFS

Regular BFS works on unweighted graphs (all edges weight 1). Dijkstra handles arbitrary non-negative weights using a priority queue. 0-1 BFS is the sweet spot in between: when weights are only 0 or 1, we can use a deque (double-ended queue) to maintain sorted order without the log(V) overhead of a heap.

Specialized BFS

0-1 BFS Algorithm

0-1 BFS is a shortest path algorithm optimized for graphs where every edge has weight 0 or 1. It uses a Deque (double-ended queue) instead of a priority queue, achieving O(V + E) time complexity - the same as regular BFS!

The key insight: When processing a vertex, 0-weight edges lead to neighbors at the same distance level, while 1-weight edges lead to the next level. By adding 0-weight neighbors to the front of the deque and 1-weight neighbors to the back, we maintain sorted order automatically.

Think of it this way: The deque naturally partitions into "current level" at the front and "next level" at the back. 0-weight edges stay in the current level (add front), 1-weight edges advance to the next level (add back). It's like BFS with a priority boost for free edges!

Key properties: Time O(V + E) - same as BFS!, uses Deque instead of PriorityQueue, only works for 0/1 weights, perfect for grid problems with obstacles (0=free, 1=break through).

Common Interview Problems: Grid traversal with obstacles, minimum cost to make path valid, shortest path with one wall removal, and any problem where costs are binary (free vs. paid).

O(V + E) Time

int[] bfs01(int n, List> adj, int source) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    
    Deque deque = new ArrayDeque<>();
    deque.addFirst(source);
}

Why Deque?

A Deque (double-ended queue) allows O(1) insertion at both front AND back. This replaces the Priority Queue used in Dijkstra!

Speed Advantage

No heap operations means O(V + E) instead of O((V+E) log V). For large graphs with 0/1 weights, this is a significant speedup!

Core Logic

    while (!deque.isEmpty()) {
        int u = deque.pollFirst();
        
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];  // w is 0 or 1
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (w == 0) {
                    deque.addFirst(v);  // Add to FRONT
                } else {
                    deque.addLast(v);   // Add to BACK
                }
            }
        }
    }
    
    return dist;
}

Weight = 0 → Front

0-weight edge means same distance level. Add to front so it's processed immediately (like BFS at same level).

Weight = 1 → Back

1-weight edge means next distance level. Add to back so current level is fully processed first.

Auto-Sorted!

This front/back strategy keeps the deque sorted by distance automatically. No heap needed!

Key Insight: Think of it as a modified BFS. In regular BFS (unweighted), all edges have weight 1 so we use a regular queue. Here, 0-weight edges are "free" so we jump to them immediately by adding to front!

Grid Application

// Example: Minimum cost to traverse grid
// '.' = free path (weight 0), '#' = obstacle (weight 1 to break)
int minCostPath(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    
    Deque deque = new ArrayDeque<>();
    deque.addFirst(new int[]{0, 0});
    dist[0][0] = grid[0][0] == '#' ? 1 : 0;
    
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};  // 4 directions
}

2D Distance Grid

Instead of 1D array, use dist[row][col] to track shortest distance to each cell. Same concept, just 2D!

Binary Weights

Free cells '.' have weight 0, obstacles '#' have weight 1 (cost to break through). Perfect for 0-1 BFS!

Grid BFS Loop

    while (!deque.isEmpty()) {
        int[] curr = deque.pollFirst();
        int r = curr[0], c = curr[1];
        
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            
            // Bounds check
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                int cost = grid[nr][nc] == '#' ? 1 : 0;
                
                if (dist[r][c] + cost < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + cost;
                    
                    if (cost == 0) {
                        deque.addFirst(new int[]{nr, nc});
                    } else {
                        deque.addLast(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    
    return dist[rows-1][cols-1];
}

4-Directional

Move up, down, left, right using direction array. Same pattern as regular grid BFS.

Bounds Check

Ensure new position is within grid before accessing. Standard grid traversal safety check.

Return Answer

Bottom-right cell dist[rows-1][cols-1] contains minimum cost to reach destination.

Common Interview Problems: "Minimum cost to make path valid", "Shortest path with obstacles elimination", "Minimum moves to reach target" - all can use 0-1 BFS when costs are binary!

Practice Questions: 0-1 BFS

Given:

Graph (node -> [(neighbor, weight)]):
0 -> [(1, 0), (2, 1)]
1 -> [(2, 0), (3, 1)]
2 -> [(3, 0)]
3 -> []

Source: 0

Task: Find shortest distances using 0-1 BFS. Show the deque state after each step.

Expected output: dist[] = {0, 0, 0, 0}

Show Solution

// Initial: dist = [0, INF, INF, INF], deque = [0]

// Process 0:
//   0->1 (w=0): dist[1] = 0, addFirst(1)
//   0->2 (w=1): dist[2] = 1, addLast(2)
//   deque = [1, 2]

// Process 1 (from front):
//   1->2 (w=0): dist[2] = min(1, 0+0) = 0, addFirst(2)
//   1->3 (w=1): dist[3] = 0+1 = 1, addLast(3)
//   deque = [2, 2, 3]

// Process 2 (from front, dist=0):
//   2->3 (w=0): dist[3] = min(1, 0+0) = 0, addFirst(3)
//   deque = [3, 2, 3]

// Process 3 (dist=0): no neighbors
// Skip duplicate 2, 3

// Final: dist = [0, 0, 0, 0]
// Path to 3: 0 -> 1 -> 2 -> 3 (all 0-weight edges!)

Given:

Grid (3x3):
. # .
# # .
. . .

'.' = free (cost 0)
'#' = obstacle (cost 1 to break)

Task: Find minimum cost to go from (0,0) to (2,2).

Expected output: 1

Show Solution

// Using 0-1 BFS on grid
// dist[0][0] = 0, deque = [(0,0)]

// Process (0,0):
//   Right (0,1)='#': cost 1, addLast
//   Down (1,0)='#': cost 1, addLast
//   deque = [(0,1), (1,0)], dist updated

// Process (0,1) with dist=1:
//   Right (0,2)='.': cost 0, dist[0][2] = 1
//   Down (1,1)='#': cost 1, dist[1][1] = 2
//   deque = [(1,0), (0,2), (1,1)]

// Process (0,2) with dist=1:
//   Down (1,2)='.': cost 0, dist[1][2] = 1
//   deque = [..., (1,2)]

// Process (1,2) with dist=1:
//   Down (2,2)='.': cost 0, dist[2][2] = 1

// Answer: 1 (break one obstacle)
// Path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
//       break '#' at (0,1), rest are '.'

Problem: You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values: 0 represents an empty cell, 1 represents an obstacle. Return the minimum number of obstacles to remove so you can move from upper left to lower right corner.

grid = [[0,1,1],
        [1,1,0],
        [1,1,0]]

Expected output: 2

Show Solution

public int minimumObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    
    Deque<int[]> deque = new ArrayDeque<>();
    deque.addFirst(new int[]{0, 0});
    dist[0][0] = grid[0][0];  // 0 if empty, 1 if obstacle
    
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    while (!deque.isEmpty()) {
        int[] curr = deque.pollFirst();
        int r = curr[0], c = curr[1];
        
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int cost = grid[nr][nc];  // 0 or 1
                
                if (dist[r][c] + cost < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + cost;
                    
                    if (cost == 0) {
                        deque.addFirst(new int[]{nr, nc});
                    } else {
                        deque.addLast(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    
    return dist[m-1][n-1];  // 2
}

// Trace:
// Best path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
// Obstacles removed: (0,1)=1 and (0,2)=1
// Total cost: 2

06

Applications and Optimizations

Shortest path algorithms power countless real-world systems. Understanding their applications helps you recognize when to use them, while knowing optimizations helps you scale solutions for production.

Real-World Applications

GPS Navigation

Google Maps, Waze, and navigation apps use modified Dijkstra with A* heuristics to find fastest routes considering traffic, road types, and real-time conditions.

Dijkstra + A*

Network Routing

Internet routers use OSPF (Dijkstra) and BGP (Bellman-Ford variant) protocols to find optimal packet routes across networks with varying latencies.

Dijkstra / Bellman-Ford

Currency Arbitrage

Financial systems detect arbitrage opportunities by finding negative cycles in currency exchange graphs using Bellman-Ford (log-transformed rates).

Bellman-Ford

Game AI Pathfinding

Video games use A* (Dijkstra + heuristic) for NPC movement, with optimizations like Jump Point Search for grid-based worlds and hierarchical pathfinding.

A* / 0-1 BFS

Social Networks

LinkedIn's "degrees of separation" and Facebook's friend suggestions use BFS/shortest path to find connections and recommend people you may know.

BFS / Dijkstra

Flight Planning

Airlines use Floyd-Warshall to precompute all city-pair distances for flight scheduling, pricing strategies, and connecting flight optimization.

Floyd-Warshall

Algorithm Optimizations

A* enhances Dijkstra by adding a heuristic function h(n) that estimates the remaining distance to the goal. Instead of picking the node with minimum dist[n], A* picks the node with minimum f(n) = dist[n] + h(n).

// A* modification to Dijkstra
// Instead of: pq.offer(new int[]{dist[v], v});
// Use:        pq.offer(new int[]{dist[v] + heuristic(v, goal), v});

int heuristic(int node, int goal) {
    // For grids: Manhattan distance
    return Math.abs(nodeX[node] - goalX) + Math.abs(nodeY[node] - goalY);
    
    // For geographic: Haversine distance (straight-line)
}

Key Insight: A* is optimal when h(n) is admissible (never overestimates). Common heuristics: Manhattan distance (grids), Euclidean distance (2D space), Haversine (Earth coordinates).

Run Dijkstra from both source and target simultaneously. When the searches meet, we've found the shortest path. This can reduce search space from O(V) to O(2 * sqrt(V)) in practice!

// Bidirectional Dijkstra concept
PriorityQueue<int[]> pqForward = new PriorityQueue<>(...);   // From source
PriorityQueue<int[]> pqBackward = new PriorityQueue<>(...);  // From target

while (!pqForward.isEmpty() && !pqBackward.isEmpty()) {
    // Alternate between forward and backward
    processOneStep(pqForward, distForward, distBackward);
    processOneStep(pqBackward, distBackward, distForward);
    
    // Check if searches have met
    if (visited by both) {
        return distForward[meetNode] + distBackward[meetNode];
    }
}

Used by: Google Maps uses bidirectional search with contraction hierarchies for continent-scale routing in milliseconds.

If you only need the shortest path to a single target (not all nodes), stop as soon as you pop the target from the priority queue!

while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int d = curr[0], u = curr[1];
    
    // EARLY EXIT: Target found with guaranteed shortest distance
    if (u == target) {
        return d;  // No need to continue!
    }
    
    if (d > dist[u]) continue;
    // ... rest of Dijkstra
}

Why it works: When we pop a node from the min-heap, we've found its shortest distance (greedy property). So when target is popped, we're guaranteed it's optimal!

For sparse graphs (E << V²), choose the right data structure:

Optimization	When to Use	Benefit
Adjacency List	Sparse graphs (E << V²)	O(V+E) space vs O(V²)
Fibonacci Heap	Very dense graphs	O(1) amortized decrease-key
Bucket Queue	Small integer weights	O(1) operations, no log factor
Dial's Algorithm	Weights in range [0, C]	O(V*C + E) time

For production systems with repeated queries on static graphs, preprocess the graph once:

Contraction Hierarchies

Precompute "shortcut" edges that skip over unimportant nodes. Query time drops from seconds to microseconds for road networks!

Transit Node Routing

Precompute distances through a small set of "transit nodes" (highway junctions). Long-distance queries become table lookups!

Hierarchical Graphs

Build multi-level graphs (local roads → highways → interstates). Search stays local until switching to higher-level roads.

All-Pairs Precomputation

For small graphs (< 1000 nodes), just precompute all shortest paths with Floyd-Warshall. O(1) query time!

Optimization Decision Guide

Single Query, Known Target?

Use A* with heuristic + early termination. Best for game pathfinding, GPS single-route.

Many Queries, Static Graph?

Use Contraction Hierarchies or precompute with Floyd-Warshall (if small). Best for map services.

Dynamic Graph (Changing Edges)?

Stick with standard Dijkstra/Bellman-Ford. Preprocessing doesn't help when graph changes frequently.

Grid with Binary Weights?

Use 0-1 BFS (deque). O(V+E) beats Dijkstra's O((V+E) log V). Perfect for maze/obstacle problems.

Practice Questions: Applications and Optimizations

Match each scenario with the best algorithm/optimization:

Finding route from your house to the airport (one-time query)
A ride-sharing app computing ETAs to thousands of nearby drivers
Detecting profitable currency exchange cycles
NPC pathfinding in a tile-based game with walls
An airline computing all city-pair distances for pricing

Show Solution

A* with early termination - Single source-target query, use heuristic to guide search toward airport
Dijkstra from your location - Single source, multiple targets (all drivers). One Dijkstra gives distances to all drivers!
Bellman-Ford - Need to detect negative cycles (arbitrage = negative cycle in log-transformed rates)
0-1 BFS - Grid with binary weights (free tiles vs walls). Deque-based O(V+E) approach
Floyd-Warshall - All-pairs shortest paths needed, precompute once for repeated queries

Given: A grid where 0 = passable, 1 = obstacle. Find shortest path from top-left to bottom-right using A* with Manhattan distance heuristic.

int[][] grid = {
    {0, 0, 0, 1, 0},
    {1, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

Show Solution

int aStarGrid(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    
    // PQ stores: {f = g + h, row, col}
    // g = actual distance, h = heuristic (Manhattan to goal)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
    
    int goalR = m-1, goalC = n-1;
    dist[0][0] = 0;
    pq.offer(new int[]{manhattan(0, 0, goalR, goalC), 0, 0});
    
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int r = curr[1], c = curr[2];
        
        // Early termination!
        if (r == goalR && c == goalC) {
            return dist[r][c];
        }
        
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n 
                && grid[nr][nc] == 0) {
                
                int newDist = dist[r][c] + 1;
                if (newDist < dist[nr][nc]) {
                    dist[nr][nc] = newDist;
                    int f = newDist + manhattan(nr, nc, goalR, goalC);
                    pq.offer(new int[]{f, nr, nc});
                }
            }
        }
    }
    return -1;  // No path
}

int manhattan(int r1, int c1, int r2, int c2) {
    return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}

// Answer: 8 (path length from (0,0) to (4,4))

Problem: Given currency exchange rates, detect if there's an arbitrage opportunity (a cycle that yields profit).

// rates[i][j] = exchange rate from currency i to j
double[][] rates = {
    {1.0,   0.5,   2.0 },  // USD -> USD, EUR, GBP
    {2.1,   1.0,   3.0 },  // EUR -> USD, EUR, GBP
    {0.45,  0.33,  1.0 }   // GBP -> USD, EUR, GBP
};
// Currencies: 0=USD, 1=EUR, 2=GBP

Show Solution

boolean hasArbitrage(double[][] rates) {
    int n = rates.length;
    
    // Convert to graph: edge weight = -log(rate)
    // Arbitrage = product > 1 = sum of logs > 0 = negative cycle!
    double[][] graph = new double[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = -Math.log(rates[i][j]);
        }
    }
    
    // Bellman-Ford from any source (use 0)
    double[] dist = new double[n];
    Arrays.fill(dist, Double.MAX_VALUE);
    dist[0] = 0;
    
    // V-1 relaxations
    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
    
    // V-th iteration: check for negative cycle
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (dist[u] + graph[u][v] < dist[v]) {
                return true;  // Arbitrage exists!
            }
        }
    }
    return false;
}

// For given rates:
// USD -> EUR -> USD = 0.5 * 2.1 = 1.05 (5% profit!)
// This is detected as a negative cycle in log-space

Key Takeaways

Dijkstra = PriorityQueue

Fastest for non-negative weights. O((V+E) log V).

Bellman-Ford = Negative

Handles negative edges. Detects negative cycles. O(VE).

Floyd-Warshall = All Pairs

Find all-pairs shortest paths. O(V³). Good for dense graphs.

0-1 BFS = Deque

When weights are 0 or 1 only. O(V+E) like regular BFS.

Relaxation is Key

All algorithms use relaxation: if dist[u] + w < dist[v], update dist[v]

Negative Cycles = Undefined

Negative cycles make shortest paths undefined - detect them first

What You'll Learn

Contents

Algorithm Comparison

What is a Shortest Path?

Shortest Path

Quick Decision Guide Which Algorithm?

Dijkstra's Algorithm

Understanding Dijkstra's Algorithm

Dijkstra's Algorithm

Dijkstra's Step-by-Step Example

Initial State

Final Distances

Priority Queue Flow

Practice Questions: Dijkstra's Algorithm

Easy Trace Dijkstra's algorithm on a simple graph

Medium Find shortest path with path reconstruction

Hard Network Delay Time (LeetCode 743)

Bellman-Ford Algorithm

Understanding Bellman-Ford

Bellman-Ford Algorithm

BFS vs Dijkstra vs Bellman-Ford

When Dijkstra Fails (Negative Edge)

Practice Questions: Bellman-Ford Algorithm

Easy Trace Bellman-Ford with negative edges

Medium Detect negative cycle in a graph

Hard Cheapest Flights Within K Stops (LeetCode 787)

Floyd-Warshall Algorithm

Understanding Floyd-Warshall

Floyd-Warshall Algorithm

Practice Questions: Floyd-Warshall Algorithm

Easy Complete the distance matrix step by step

Medium Detect if graph is strongly connected

Hard Find the City With Smallest Number of Reachable Neighbors (LeetCode 1334)

0-1 BFS

Understanding 0-1 BFS

0-1 BFS Algorithm

Practice Questions: 0-1 BFS

Easy Trace 0-1 BFS on a simple graph

Medium Grid traversal with obstacle breaking

Hard Minimum Obstacle Removal to Reach Corner (LeetCode 2290)

Applications and Optimizations

Real-World Applications

GPS Navigation

Network Routing

Currency Arbitrage

Game AI Pathfinding

Social Networks

Flight Planning

Algorithm Optimizations

Dijkstra++ A* Algorithm - Heuristic-Guided Search

2x Faster Bidirectional Dijkstra - Meet in the Middle

Quick Win Early Termination - Stop When Found

Memory Sparse Graph Optimizations

Production Preprocessing Techniques for Production

Contraction Hierarchies

Transit Node Routing

Hierarchical Graphs

All-Pairs Precomputation

Optimization Decision Guide

Single Query, Known Target?

Many Queries, Static Graph?

Dynamic Graph (Changing Edges)?

Grid with Binary Weights?

Practice Questions: Applications and Optimizations

Easy Choose the right algorithm for each scenario

Medium Implement A* for grid pathfinding

Hard Detect currency arbitrage opportunity

Key Takeaways

Dijkstra = PriorityQueue

Bellman-Ford = Negative

Floyd-Warshall = All Pairs

0-1 BFS = Deque

Relaxation is Key

Negative Cycles = Undefined

Knowledge Check