DSA Shortest Path

Shortestpath: Dijkstra's Algorithm

In our previous tutorials, we covered how to traverse graphs layer by layer using Breadth-First Search (BFS). While BFS is fantastic for finding the shortest path in an unweighted graph, real-world data is rarely that simple.

What happens when the edges have different costs, distances, or times attached to them? You need an algorithm that can mathematically weigh the options.

1. Why Shortest Path Algorithms Matter

Shortest path algorithms power the systems that drive the modern world. Here are just a few real-life applications:

1. GPS Navigation (Google Maps): Finding the fastest driving route between City A and City B where edges are roads and weights are estimated driving times.
2. Network Routing: Determining the most efficient path for data packets to travel across the internet through various servers and routers.
3. Social Networks: Finding the shortest connection of mutual friends between two users (e.g., LinkedIn's "3rd-degree connection" feature).
4. Game Development: AI pathfinding to help non-player characters (NPCs) navigate around obstacles to reach the player.

2. Introducing Dijkstra's Algorithm

Created by computer scientist Edsger W. Dijkstra in 1956, this algorithm guarantees the absolute shortest path from a starting node to all other nodes in a Weighted Directed or Undirected Graph—as long as there are no negative edge weights.

Instead of blindly exploring every node like BFS, Dijkstra's algorithm uses a Greedy Approach. It constantly asks: "Of all the nodes I can currently reach, which one is the cheapest to get to?"

A Directed Weighted Graph. The Shortest Path from A to E is highlighted, successfully avoiding the misleadingly simple direct routes.

3. How Dijkstra Works (Step-by-Step)

To efficiently find the cheapest next step, Dijkstra's algorithm relies on a Min-Heap (Priority Queue) and a table of distances.

The Logic

1. Initialize Distances: Create a table tracking the minimum distance to every node. Set the starting node's distance to 0, and all other nodes to Infinity.
2. Use a Priority Queue: Push the starting node into a Min-Heap queue with a cost of 0.
3. Extract the Minimum: While the queue is not empty, pop the node with the lowest current cost.
4. Explore Neighbors (Relaxation): For the popped node, look at all its immediate neighbors. Calculate the total cost to reach the neighbor through this current node.
5. Update if Cheaper: If this newly calculated cost is lower than the neighbor's currently known distance, update the table and push the neighbor into the queue with this new cheaper cost.
6. Repeat: Continue until the queue is empty.

By the end of this loop, your distance table will contain the absolute minimum cost required to reach every single node in the graph from your starting point!

4. Implementing Dijkstra in Python

Python's heapq module is perfect for the Priority Queue required by Dijkstra's algorithm. Let's write the code to solve the exact graph illustrated in the image above.

import heapq

def dijkstra(graph, start):
    # 1. Initialize distances to Infinity
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # Priority Queue holds tuples of (current_cost, node)
    priority_queue = [(0, start)]
    while priority_queue:
        # 2. Pop the node with the lowest cost
        current_distance, current_node = heapq.heappop(priority_queue)
        # Optimization: Ignore if we already found a better path earlier
        if current_distance > distances[current_node]:
            continue
        # 3. Check all adjacent neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # 4. If new path is cheaper, update and push to queue
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances
# Graph from the SVG diagram (Adjacency List with Dictionary)
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'D': 5},
    'C': {'B': 1, 'D': 8, 'E': 10},
    'D': {'E': 2},
    'E': {}
}
shortest_paths = dijkstra(graph, 'A')
print("Shortest path costs from A:", shortest_paths)
# Output: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

5. Reconstructing the Exact Path

The basic implementation above gives you the minimum cost to reach every node. But what if your application actually needs to print the physical route (e.g., A -> C -> B -> D -> E)?

To achieve this, you simply need to keep track of the "Previous Node" every time you update a cheaper distance. Once the algorithm finishes, you can trace backward from your destination to your start.

Example Modification

Inside the update block (Step 4), simply add: previous_nodes[neighbor] = current_node

6. Complexity Analysis

The time complexity of Dijkstra heavily depends on the data structure used to find the minimum distance node. By using a Binary Min-Heap (like Python's heapq), we achieve stellar performance:

• Time Complexity: O((V + E) log V) — We extract the minimum vertex up to V times, and we push onto the heap up to E times. Each heap operation takes log V time.
• Space Complexity: O(V) — For the distances dictionary and the priority queue size.

7. The Fatal Flaw: Negative Weights

Dijkstra's Algorithm operates on the fundamental assumption that adding an edge to a path never makes the path shorter. It assumes all weights are ≥ 0.

If your graph contains Negative Edge Weights (e.g., a financial graph where an edge represents a profit or tax rebate), Dijkstra's Greedy Approach will fail and return incorrect results.

If you suspect your graph has negative weights, you must abandon Dijkstra and instead use the Bellman-Ford Algorithm, which is slightly slower but safely handles negative numbers.