Shortest Path Algorithms (Dijkstra)

# CHAPTER 26

Shortest Path Algorithms (Dijkstra) #

1. Introduction #

2. Learning Objectives #

• Explain the cumulative distance tracking mechanism.

• Understand the integration of the Min-Heap Priority Queue.

• Trace the aggressive "Relaxation" of geometric paths.

• Analyze the $O(E \log V)$ Time Complexity.

• Identify the fatal flaw regarding Negative Edge Weights.

3. The Execution Logic #

The Core Mechanisms:

1. 1. The Distance Array: Create an array tracking the shortest known distance to every node. Initialize the Start Node to 0, and all others to Infinity.

1. 2. The Priority Queue (Min-Heap): Just like Prim's algorithm, Dijkstra throws pathways into a Min-Heap so it can aggressively extract the absolute cheapest, shortest available path.

1. 3. The Relaxation Process: When Dijkstra extracts a Node, it evaluates all of its outgoing neighbors. It calculates: *(Distance to Current Node) + (Weight of Edge to Neighbor)*.

• If this new cumulative total is less than the currently known Infinity (or previously recorded distance) to that Neighbor, we physically overwrite the array with the new lower number! We have "Relaxed" the path.

4. Visualizing the Traversal #

1. 1. Start at A. Distance Array: [A:0, B:∞, C:∞].

1. 2. Evaluate A's neighbors (B and C).

• Path A->B: 0 + 5 = 5. Is 5 < ∞? Yes! Update B to 5.

• Path A->C: 0 + 10 = 10. Is 10 < ∞? Yes! Update C to 10.

• Array is now: [A:0, B:5, C:10].

1. 3. Greedy Move! The Min-Heap extracts the absolute smallest available node (B).

1. 4. Evaluate B's neighbors (C).

• Path B->C: Current Distance to B (5) + Weight of B->C (2) = 7.

• Is 7 < 10? YES! We found a faster backdoor route! We overwrite the old data.

• Final Array: [A:0, B:5, C:7].

5. Implementation in Code #

// Java Example: Dijkstra's Algorithm
import java.util.*;

public class Dijkstra {
    
    // A helper class to store Node and Distance in the Queue
    static class Node implements Comparable<Node> {
        int vertex, weight;
        Node(int v, int w) { vertex = v; weight = w; }
        public int compareTo(Node n) { return Integer.compare(this.weight, n.weight); }
    }

    public void calculateShortestPath(int start, List<List<Node>> adjList, int V) {
        // 1. Initialize Distance Array to Infinity
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0; // Distance to itself is 0
        
        // 2. Initialize Min-Heap Priority Queue
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        // 3. Execution Engine
        while (!pq.isEmpty()) {
            // Extract the closest geometric node!
            Node current = pq.poll();
            
            // 4. Evaluate Neighbors
            for (Node neighbor : adjList.get(current.vertex)) {
                
                // The mathematical "Relaxation" evaluation!
                int newDist = dist[current.vertex] + neighbor.weight;
                
                // If the new cumulative distance is structurally cheaper...
                if (newDist < dist[neighbor.vertex]) {
                    
                    dist[neighbor.vertex] = newDist; // Overwrite the old record!
                    pq.add(new Node(neighbor.vertex, newDist)); // Throw into Queue!
                }
            }
        }
        
        // At completion, the 'dist' array holds the absolute fastest route to ALL nodes!
    }
}

6. Complexity Analysis #

7. The Catastrophic Weakness: Negative Weights #

What if a mathematical graph contains an Edge with a Weight of -50? Dijkstra's logic violently shatters. It extracts a node, falsely believes it has found the shortest localized path, locks it, and completely ignores the massive -50 backdoor shortcut hidden deeper in the graph! *Rule: Dijkstra mathematically CANNOT process graphs containing Negative Edge Weights.*

8. Real-World Applications #

1. 1. Google Maps / Waze Navigation: Dijkstra calculates the absolute fastest physical driving route by mapping intersections as Vertices, roads as Edges, and traffic delays as Weights.

1. 2. OSPF Routing Protocol: Internet infrastructure routers actively use Dijkstra to map the global topology of data centers, calculating the lowest-latency fiber-optic paths to bounce data packets.

9. Common Mistakes #

• Forgetting the Priority Queue: If a junior developer tries to write Dijkstra using a standard array to find the minimum node, the algorithm degrades from a lightning-fast $O(E \log V)$ to a catastrophic $O(V^2)$, violently crashing on large graphs. You must explicitly use a Min-Heap.

10. Exercises #

1. 1. If a Graph has a pathway A->B (Weight 10) and B->C (Weight -20), trace why Dijkstra's algorithm might finalize C with an incorrect higher distance.

1. 2. What is the fundamental difference in the Relaxation logic between Dijkstra's algorithm and Prim's algorithm? *(Hint: Look at the cumulative addition).*

11. MCQs with Answers #

12. Interview Preparation #

• *System Modification:* "Dijkstra calculates the distance, but how do I physically print the actual path (e.g., A -> B -> C)?" *(Answer: Maintain a PreviousNode array alongside the Distance array! Every time you successfully execute a 'Relaxation', explicitly record Prev[neighbor] = current. When the algorithm finishes, start at the Destination and trace the Prev array backwards to the Start!)*

13. Summary #

14. Next Chapter Recommendation #