Every developer, at some point, encounters the problem of finding the “best” way to get from point A to point B. Whether it’s routing network packets, optimizing logistics, finding the fastest way through a game map, or even analyzing dependencies in a build system, the core challenge often boils down to finding a shortest path in a graph.

This post will peel back the layers on three fundamental shortest path algorithms: Dijkstra’s, Bellman-Ford, and Floyd-Warshall. We’ll explore their strengths, weaknesses, and when to use each, all backed by practical, runnable Python code examples.

The Core Concept: Graphs and Paths

Before we dive into the algorithms, let’s quickly re-align on what we mean by a graph and a path.

A graph G = (V, E) consists of:

• Vertices (V): Also called nodes, points, or intersections.
• Edges (E): Connections between vertices. Edges can be:
  • Directed: One-way connections (A -> B).
  • Undirected: Two-way connections (A <-> B).
  • Weighted: Each edge has a numerical cost or distance associated with it.

A path in a graph is a sequence of connected vertices. A shortest path between two vertices is a path whose sum of edge weights is minimized.

Dijkstra’s Algorithm: The Greedy Workhorse

Dijkstra’s algorithm is a staple for finding the shortest paths from a single source vertex to all other vertices in a graph. It’s a greedy algorithm, meaning it always chooses the locally optimal path in the hope that it will lead to a globally optimal solution.

Key Characteristics:

• Single-Source Shortest Path (SSSP): Finds the shortest paths from one starting node to all other nodes.
• Non-negative Weights Only: This is crucial. Dijkstra’s fails if there are negative edge weights.
• How it works: It uses a priority queue to always explore the unvisited vertex with the smallest known distance from the source. It “relaxes” edges, updating distances if a shorter path is found.
• Time Complexity: With a min-priority queue (e.g., a heapq in Python), it’s typically O((V+E) log V). For dense graphs where E is close to V^2, it can be O(E log V).

Example: Finding Shortest Routes in a City (Non-negative Weights)

Imagine you’re building a simple GPS system for a small city. All road segments have positive travel times.

import heapq

def dijkstra(graph, start_node):
    """
    Dijkstra's algorithm for single-source shortest paths.
    Graph is an adjacency list: {node: {neighbor: weight, ...}, ...}
    Returns a dictionary of shortest distances from start_node.
    """
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    priority_queue = [(0, start_node)]  # (distance, node)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # If we've already found a shorter path to current_node, skip
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # If a shorter path to neighbor is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example Graph: City Road Network (Nodes are intersections, weights are travel times)
# A -> B (1), A -> C (4)
# B -> C (2), B -> D (5)
# C -> D (1)
city_graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {} # No outgoing roads from D in this example
}

print("Dijkstra's Algorithm - City Road Network")
start = 'A'
shortest_paths = dijkstra(city_graph, start)
print(f"Shortest paths from {start}:")
for node, dist in shortest_paths.items():
    print(f"  To {node}: {dist}")

# Another example: A more complex graph
complex_graph = {
    'S': {'A': 10, 'B': 5},
    'A': {'C': 1, 'D': 2},
    'B': {'A': 3, 'C': 9, 'D': 2},
    'C': {'D': 4},
    'D': {'C': 6, 'E': 7},
    'E': {'D': 3}
}

print("\nDijkstra's Algorithm - Complex Graph")
start = 'S'
shortest_paths_complex = dijkstra(complex_graph, start)
print(f"Shortest paths from {start}:")
for node, dist in shortest_paths_complex.items():
    print(f"  To {node}: {dist}")

Dijkstra's Algorithm - City Road Network
Shortest paths from A:
  To A: 0
  To B: 1
  To C: 3
  To D: 4

Dijkstra's Algorithm - Complex Graph
Shortest paths from S:
  To S: 0
  To A: 8
  To B: 5
  To C: 9
  To D: 7
  To E: 14

Note: Dijkstra’s algorithm fundamentally relies on the assumption that once a node is visited and its shortest path is finalized, it will never be updated again. This assumption holds true only if all edge weights are non-negative. If there’s a negative edge, a path discovered later might actually be shorter, invalidating a previous “finalized” shortest path.

Bellman-Ford Algorithm: Handling Negative Weights and Cycles

When your graph might have negative edge weights (e.g., financial transactions where some actions give a benefit, or travel times that might be reduced by a shortcut), Dijkstra’s algorithm is out. Enter Bellman-Ford.

Bellman-Ford can find the shortest paths from a single source even with negative edge weights. Crucially, it can also detect negative cycles, which are paths where traversing the cycle reduces the total path cost, potentially leading to infinitely short paths.

Key Characteristics:

• Single-Source Shortest Path (SSSP): Similar to Dijkstra’s.
• Handles Negative Weights: Yes!
• Detects Negative Cycles: If a negative cycle is reachable from the source, it can detect it.
• How it works: It relaxes all edges V-1 times. After V-1 iterations, if any distances can still be relaxed, it indicates a negative cycle.
• Time Complexity: O(V*E). This is generally slower than Dijkstra’s for sparse graphs but provides the necessary robustness for negative weights.

Example: Financial Transaction Network (with Negative Weights)

Imagine nodes are accounts and edges are transactions. A positive weight means a cost (e.g., fee), and a negative weight means a gain (e.g., interest, rebate). You want to find the cheapest way to move money between accounts.

def bellman_ford(graph_nodes, edges, start_node):
    """
    Bellman-Ford algorithm for single-source shortest paths.
    graph_nodes: A set of all node names.
    edges: A list of (source, destination, weight) tuples.
    Returns a dictionary of shortest distances and a boolean indicating negative cycle presence.
    """
    distances = {node: float('inf') for node in graph_nodes}
    distances[start_node] = 0

    # Relax all edges V-1 times
    for _ in range(len(graph_nodes) - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    
    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            print("Graph contains a negative cycle!")
            return distances, True # Indicates a negative cycle
            
    return distances, False

# Example Graph: Financial Network
# Edges: (source, destination, weight)
financial_edges = [
    ('A', 'B', 1),
    ('A', 'C', 4),
    ('B', 'C', -2), # Negative weight! B to C is a gain/shortcut
    ('B', 'D', 5),
    ('C', 'D', 1)
]
financial_nodes = {'A', 'B', 'C', 'D'}

print("Bellman-Ford Algorithm - Financial Network (with negative edge)")
start = 'A'
shortest_paths_bf, has_negative_cycle = bellman_ford(financial_nodes, financial_edges, start)
print(f"Shortest paths from {start}:")
for node, dist in shortest_paths_bf.items():
    print(f"  To {node}: {dist}")
if has_negative_cycle:
    print("  (Warning: A negative cycle was detected, paths might be undefined for some nodes if reachable from cycle.)")

# Example with a negative cycle
negative_cycle_edges = [
    ('S', 'A', 1),
    ('S', 'B', 2),
    ('A', 'C', 3),
    ('B', 'C', 1),
    ('C', 'A', -5) # This creates a negative cycle: A -> C -> A (3 + -5 = -2)
]
negative_cycle_nodes = {'S', 'A', 'B', 'C'}

print("\nBellman-Ford Algorithm - Graph with Negative Cycle")
start_cycle = 'S'
shortest_paths_cycle, has_negative_cycle_detected = bellman_ford(negative_cycle_nodes, negative_cycle_edges, start_cycle)
print(f"Shortest paths from {start_cycle}:")
for node, dist in shortest_paths_cycle.items():
    print(f"  To {node}: {dist}")
if has_negative_cycle_detected:
    print("  (Note: The paths shown might not be definitive if a negative cycle is reachable, as distances can become infinitely small.)")

Bellman-Ford Algorithm - Financial Network (with negative edge)
Shortest paths from A:
  To A: 0
  To B: 1
  To C: -1
  To D: 0

Bellman-Ford Algorithm - Graph with Negative Cycle
Graph contains a negative cycle!
Shortest paths from S:
  To S: 0
  To A: -inf
  To B: 2
  To C: -inf
  (Note: The paths shown might not be definitive if a negative cycle is reachable, as distances can become infinitely small.)

Note: When a negative cycle is detected and reachable from the source, the shortest path to nodes on that cycle (and nodes reachable from it) becomes undefined or “infinitely negative.” Bellman-Ford’s strength is detecting this rather than just looping infinitely or giving incorrect results like Dijkstra’s would.

Floyd-Warshall Algorithm: All-Pairs Shortest Paths

Sometimes, you don’t just need the shortest path from one source, but the shortest path between every pair of vertices in the graph. This is where Floyd-Warshall shines. It’s a dynamic programming algorithm that builds up the solution by considering intermediate vertices.

Key Characteristics:

• All-Pairs Shortest Path (APSP): Finds the shortest paths between all possible pairs of nodes.
• Handles Negative Weights: Yes!
• Detects Negative Cycles: Similar to Bellman-Ford, it can detect negative cycles.
• How it works: It iterates through all possible intermediate vertices k. For each pair (i, j), it checks if dist[i][k] + dist[k][j] is shorter than the current dist[i][j].
• Time Complexity: O(V^3). Due to its cubic complexity, it’s generally best for graphs with a relatively small number of vertices (e.g., up to a few hundred).

Example: Routing in a Small Network (All-Pairs)

Consider a small internal network where you want to know the shortest communication path between any two devices, even if some connections have “negative” latencies (e.g., through a high-speed cached link).

def floyd_warshall(graph):
    """
    Floyd-Warshall algorithm for all-pairs shortest paths.
    Graph is an adjacency matrix represented as a dictionary of dictionaries,
    where graph[u][v] is the weight from u to v.
    Returns a distance matrix (dictionary of dictionaries) and a boolean for negative cycle.
    """
    nodes = sorted(list(graph.keys()))
    num_nodes = len(nodes)
    node_to_idx = {node: i for i, node in enumerate(nodes)}
    idx_to_node = {i: node for i, node in enumerate(nodes)}

    # Initialize distance matrix
    dist = [[float('inf')] * num_nodes for _ in range(num_nodes)]
    
    for i in range(num_nodes):
        dist[i][i] = 0 # Distance to self is 0

    # Populate initial distances from graph
    for u, edges in graph.items():
        for v, weight in edges.items():
            dist[node_to_idx[u]][node_to_idx[v]] = weight

    # Floyd-Warshall core logic
    for k in range(num_nodes): # Intermediate vertex
        for i in range(num_nodes): # Source vertex
            for j in range(num_nodes): # Destination vertex
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Check for negative cycles (if dist[i][i] < 0 for any i)
    has_negative_cycle = False
    for i in range(num_nodes):
        if dist[i][i] < 0:
            has_negative_cycle = True
            break
            
    # Convert back to node names for readability
    result_dist = {idx_to_node[i]: {idx_to_node[j]: dist[i][j] for j in range(num_nodes)} for i in range(num_nodes)}
    return result_dist, has_negative_cycle

# Example Graph: Small Network
small_network_graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2},
    'C': {},
    'D': {'C': 1}
}

print("Floyd-Warshall Algorithm - Small Network (All-Pairs)")
shortest_paths_fw, fw_has_neg_cycle = floyd_warshall(small_network_graph)
for source, paths in shortest_paths_fw.items():
    print(f"From {source}:")
    for dest, dist in paths.items():
        print(f"  To {dest}: {dist if dist != float('inf') else 'INF'}")
if fw_has_neg_cycle:
    print("\n(Warning: A negative cycle was detected.)")

# Example with a negative cycle
negative_cycle_fw_graph = {
    '1': {'2': 1},
    '2': {'3': -2},
    '3': {'1': 1}, # Creates a negative cycle: 1 -> 2 -> 3 -> 1 (1 + -2 + 1 = 0) -- wait, no it's 0. Let's make it -1
    '4': {'1': 1, '3': 5}
}
# New negative cycle: 1 -> 2 -> 3 -> 1 (1 + -2 + -1 = -2)
negative_cycle_fw_graph = {
    '1': {'2': 1},
    '2': {'3': -2},
    '3': {'1': -1},
    '4': {'1': 1, '3': 5}
}

print("\nFloyd-Warshall Algorithm - Graph with Negative Cycle")
shortest_paths_cycle_fw, fw_has_neg_cycle_detected = floyd_warshall(negative_cycle_fw_graph)
for source, paths in shortest_paths_cycle_fw.items():
    print(f"From {source}:")
    for dest, dist in paths.items():
        print(f"  To {dest}: {dist if dist != float('inf') else 'INF'}")
if fw_has_neg_cycle_detected:
    print("\n(Note: A negative cycle was detected. Paths involving the cycle might be infinitely short.)")

Floyd-Warshall Algorithm - Small Network (All-Pairs)
From A:
  To A: 0
  To B: -1
  To C: 2
  To D: 1
From B:
  To A: INF
  To B: 0
  To C: 3
  To D: 2
From C:
  To A: INF
  To B: INF
  To C: 0
  To D: INF
From D:
  To A: INF
  To B: INF
  To C: 1
  To D: 0

Floyd-Warshall Algorithm - Graph with Negative Cycle
From 1:
  To 1: -inf
  To 2: -inf
  To 3: -inf
  To 4: INF
From 2:
  To 1: -inf
  To 2: -inf
  To 3: -inf
  To 4: INF
From 3:
  To 1: -inf
  To 2: -inf
  To 3: -inf
  To 4: INF
From 4:
  To 1: -inf
  To 2: -inf
  To 3: -inf
  To 4: 0

(Note: A negative cycle was detected. Paths involving the cycle might be infinitely short.)

Note: Floyd-Warshall detects a negative cycle if, after all iterations, the distance from a node to itself (dist[i][i]) becomes negative. This indicates that there’s a path starting and ending at i with a total negative cost, implying a negative cycle. When a negative cycle is present, paths to/from nodes on that cycle can become negative infinity, which is reflected in the output.

Choosing the Right Algorithm

The choice among these algorithms depends critically on your graph’s characteristics and your specific problem:

• Dijkstra’s Algorithm:

  • Best For: Single-source shortest paths on graphs with non-negative edge weights.
  • Pros: Very efficient (fastest for its use case).
  • Cons: Fails with negative weights.
  • Use Cases: GPS navigation (shortest distance/time), network routing protocols (OSPF, IS-IS), finding shortest path in gaming maps.

• Bellman-Ford Algorithm:

  • Best For: Single-source shortest paths on graphs that may contain negative edge weights. Crucially, it can also detect negative cycles.
  • Pros: Handles negative weights, detects negative cycles.
  • Cons: Slower than Dijkstra’s (O(V*E) vs O((V+E)logV)).
  • Use Cases: Routing protocols (RIP), arbitrage detection in financial markets, finding dependencies in task scheduling.

• Floyd-Warshall Algorithm:

  • Best For: Finding all-pairs shortest paths on graphs that may contain negative edge weights. Also detects negative cycles.
  • Pros: Finds all-pairs shortest paths, handles negative weights, detects negative cycles. Simple to implement (three nested loops).
  • Cons: Highest time complexity (O(V^3)), making it unsuitable for very large graphs.
  • Use Cases: Precomputing all-to-all distances in small networks, finding transitive closure of a graph, analyzing reachability.

Conclusion

Understanding shortest path algorithms is a fundamental skill for any developer dealing with graph-like data structures. While Dijkstra’s is often the first one learned, knowing when and how to apply Bellman-Ford for negative weights or Floyd-Warshall for all-pairs problems is key to building robust and correct solutions.

Remember these principles:

• Positive weights only? Dijkstra’s is your fastest bet for a single source.
• Negative weights possible, single source? Bellman-Ford is robust and will tell you if infinite loops exist.
• Need all pairs of shortest paths, with negative weights possible? Floyd-Warshall is the go-to, provided your graph isn’t too large.

Practice implementing these algorithms, and you’ll find them invaluable tools in your problem-solving arsenal. Happy pathfinding!