DSA Shortest Path

A shortest path algorithm finds the cheapest route between two nodes in a graph. Navigation apps use this idea to pick the fastest road. Delivery planners, network routers, and game maps rely on it too.

Consider a trip between two cities. Several roads connect them, and each road has a distance. Some routes look short on the map yet pass through many slow stops. The goal is to add up the road costs and choose the smallest total.

Weighted Graphs

A weighted graph attaches a number to every edge. The number can stand for distance, time, or price. The cost of a path equals the sum of its edge weights.

        4
   A ------- B
   |       / |
 2 |   1  /  | 5
   |    /    |
   C ------- D
        8

The direct route A to B costs 4. The route A to C to B costs 2 + 1 = 3, which is cheaper.

Storing Weights

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8)],
    "D": [("B", 5), ("C", 8)]
}

Each neighbor appears as a pair of node name and edge weight.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from one starting node to all other nodes. The algorithm works on graphs with no negative weights.

The Idea

• Set the distance to the start node as 0 and all others as infinity.
• Pick the unvisited node with the smallest known distance.
• Check each neighbor. When the route through the current node costs less, update the neighbor's distance.
• Mark the current node as done and repeat.

A priority queue keeps the closest node ready at the front. Python offers one through the heapq module.

The Code

import heapq

def dijkstra(graph, start):
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    queue = [(0, start)]

    while queue:
        current_cost, node = heapq.heappop(queue)
        if current_cost > distance[node]:
            continue
        for neighbor, weight in graph[node]:
            new_cost = current_cost + weight
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))
    return distance

print(dijkstra(graph, "A"))
# {'A': 0, 'B': 3, 'C': 2, 'D': 8}

Walking Through the Example

Start: A=0, B=inf, C=inf, D=inf

Visit A (0)
  B: 0 + 4 = 4   update B = 4
  C: 0 + 2 = 2   update C = 2

Visit C (2)
  B: 2 + 1 = 3   update B = 3
  D: 2 + 8 = 10  update D = 10

Visit B (3)
  D: 3 + 5 = 8   update D = 8

Visit D (8)
  nothing to improve

Final: A=0, B=3, C=2, D=8

Recovering the Actual Route

Distances alone do not show the path. A second dictionary can remember the previous node for each update.

def dijkstra_path(graph, start, end):
    distance = {node: float("inf") for node in graph}
    previous = {}
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        cost, node = heapq.heappop(queue)
        if cost > distance[node]:
            continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                previous[neighbor] = node
                heapq.heappush(queue, (new_cost, neighbor))
    path = [end]
    while path[-1] != start:
        path.append(previous[path[-1]])
    return path[::-1]

print(dijkstra_path(graph, "A", "D"))   # ['A', 'C', 'B', 'D']

Choosing the Right Method

• BFS suits graphs where every edge costs the same.
• Dijkstra suits graphs with different positive weights.
• Bellman-Ford handles negative weights and detects negative cycles, at a higher cost in time.

Complexity of Dijkstra

With a priority queue, the running time is O((V + E) log V). Space is O(V) for the distance table and the queue.

Real-Life Uses

Map apps turn road networks into weighted graphs and run a shortest path search between your location and the destination. Airlines plan routes that cut travel time or fuel. Internet routers pick the quickest path for data packets. Game characters use the same idea to walk around obstacles toward a goal.

Common Mistakes

Negative weights break Dijkstra's logic, because a visited node might later gain a cheaper route. Use Bellman-Ford for those graphs. Forgetting the skip check, which ignores outdated queue entries, wastes time without changing the answer. Test the code on a graph small enough to solve by hand.

Reading Results Carefully

A distance of infinity in the final table means the node is unreachable from the start. Two different routes can share the same lowest cost, and the algorithm returns one of them. Verify results by adding the edge weights along the returned path and comparing the sum with the stored distance.

Key Points

• Shortest path algorithms find the lowest-cost route between nodes.
• Weighted graphs attach a cost to each edge.
• Dijkstra always expands the closest unvisited node first.
• A priority queue makes Dijkstra efficient.
• Dijkstra fails on graphs with negative edge weights.
• A previous-node dictionary rebuilds the path itself.