Shortest Path

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

Core Idea

1. Maintain distance to each vertex (initialize source as 0, others as ∞)
2. Use a priority queue to always process the closest unvisited vertex
3. Relax edges: if path through current vertex is shorter, update distance

Implementation

import java.util.*;

public class Dijkstra {
    
    // Using priority queue (min-heap)
    public int[] dijkstra(List<int[]>[] graph, int start, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // PriorityQueue stores {distance, vertex}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0];
            int u = current[1];
            
            // Skip if we already found a shorter path
            if (d > dist[u]) continue;
            
            for (int[] edge : graph[u]) {
                int v = edge[0];
                int weight = edge[1];
                
                // Relaxation
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        return dist;
    }
}

Dijkstra with Path Reconstruction

public int[] dijkstraWithPath(List<int[]>[] graph, int start, int n) {
    int[] dist = new int[n];
    int[] prev = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(prev, -1);
    dist[start] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, start});
    
    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int d = current[0];
        int u = current[1];
        
        if (d > dist[u]) continue;
        
        for (int[] edge : graph[u]) {
            int v = edge[0];
            int weight = edge[1];
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    
    return dist;
}

// Reconstruct path from start to target
public List<Integer> getPath(int[] prev, int target) {
    List<Integer> path = new ArrayList<>();
    for (int v = target; v != -1; v = prev[v]) {
        path.add(v);
    }
    Collections.reverse(path);
    return path;
}

Complexity Analysis

Operation	Time	Space
Dijkstra (binary heap)	O((V + E) log V)	O(V)
Dijkstra (fibonacci heap)	O(E + V log V)	O(V)

Limitations

• No negative weights: Dijkstra doesn't work with negative edges
• No negative cycles: Algorithm assumes optimal substructure

When to Use

• Single-source shortest path in non-negative weighted graph
• Network routing protocols (OSPF)
• GPS navigation systems

Bellman-Ford Algorithm

Bellman-Ford handles negative edge weights and can detect negative cycles.

public class BellmanFord {
    
    public int[] bellmanFord(int n, int[][] edges, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int weight = edge[2];
                
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
        
        // Check for negative cycles
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                throw new RuntimeException("Negative cycle detected!");
            }
        }
        
        return dist;
    }
}

Floyd-Warshall Algorithm

Finds shortest paths between all pairs of vertices.

public class FloydWarshall {
    
    public int[][] floydWarshall(int n, int[][] edges) {
        int[][] dist = new int[n][n];
        
        // Initialize: ∞ for no edge, 0 for same vertex
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // Avoid overflow
            dist[i][i] = 0;
        }
        
        // Add edges
        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
        }
        
        // Floyd-Warshall: try all intermediate vertices
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        return dist;
    }
}

Algorithm Comparison

Algorithm	Time	Space	Negative Weights	Use Case
Dijkstra	O((V+E) log V)	O(V)	❌ No	Single-source, non-negative
Bellman-Ford	O(V × E)	O(V)	✅ Yes	Single-source, negative edges
Floyd-Warshall	O(V³)	O(V²)	✅ Yes	All-pairs shortest path

When to Use Each

Scenario	Best Algorithm
Single source, non-negative weights	Dijkstra
Single source, negative weights	Bellman-Ford
All pairs shortest path	Floyd-Warshall
Detect negative cycle	Bellman-Ford
Dense graph, all pairs	Floyd-Warshall
Sparse graph, single source	Dijkstra

Network Delay Time (Dijkstra Template)

public int networkDelayTime(int[][] times, int n, int k) {
    List<int[]>[] graph = new ArrayList[n + 1];
    for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
    
    for (int[] time : times) {
        graph[time[0]].add(new int[]{time[1], time[2]});
    }
    
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{k, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0], d = curr[1];
        if (d > dist[node]) continue;
        
        for (int[] edge : graph[node]) {
            int next = edge[0], weight = edge[1];
            if (dist[node] + weight < dist[next]) {
                dist[next] = dist[node] + weight;
                pq.offer(new int[]{next, dist[next]});
            }
        }
    }
    
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        max = Math.max(max, dist[i]);
    }
    return max;
}