Shortest Path Algorithms

Shortest path algorithms find the minimum distance (or cost) between vertices in a weighted graph. They are fundamental to GPS navigation, network routing, and game AI pathfinding.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. It uses a greedy approach: always expand the closest unvisited vertex.

import heapq

def dijkstra(graph, start):
    INF = float('inf')
    dist = [INF] * graph.n
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

How it works

1. Initialize distances: source = 0, all others = infinity
2. Push the source into a min-heap priority queue
3. Pop the vertex with the smallest distance
4. For each neighbor, if a shorter path is found, update its distance and push it onto the heap
5. Repeat until the heap is empty

Bellman-Ford Algorithm

Bellman-Ford solves the single-source shortest path problem even when edges have negative weights. It can also detect negative cycles (cycles whose total weight is negative).

def bellman_ford(graph, start):
    INF = float('inf')
    dist = [INF] * graph.n
    dist[start] = 0

    # Relax all edges V-1 times
    for _ in range(graph.n - 1):
        for u in range(graph.n):
            for v, w in graph.adj[u]:
                if dist[u] != INF and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

    # Check for negative cycles
    for u in range(graph.n):
        for v, w in graph.adj[u]:
            if dist[u] != INF and dist[u] + w < dist[v]:
                return None  # Negative cycle detected
    return dist

Why V − 1 iterations?

In a graph with V vertices, the shortest path between any two vertices can have at most V − 1 edges (a simple path without cycles). Each iteration relaxes all edges, and after k iterations, the algorithm has found all shortest paths with at most k edges.

Floyd-Warshall Algorithm

Floyd-Warshall finds the shortest paths between all pairs of vertices in O(V³) time. It works with negative weights (but not negative cycles) and is implemented with dynamic programming.

def floyd_warshall(graph):
    INF = float('inf')
    n = graph.n
    dist = [[INF] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
        for j, w in graph.adj[i]:
            dist[i][j] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

A* Search Algorithm

A* is a heuristic-based shortest path algorithm widely used in games and robotics. It combines Dijkstra's cost from the start with a heuristic estimate of the cost to the goal (e.g., Euclidean or Manhattan distance).

import heapq

def a_star(graph, start, goal, heuristic):
    open_set = [(0, start)]
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return g_score[current]

        for neighbor, weight in graph.adj[current]:
            tentative_g = g_score[current] + weight
            if tentative_g < g_score.get(neighbor, float('inf')):
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    return None

When to use which?

• Dijkstra: non-negative weights, single source, guarantees optimality
• Bellman-Ford: handles negative weights, detects negative cycles
• Floyd-Warshall: all-pairs shortest paths, dense graphs
• A*: fast point-to-point search with a good heuristic