Dijkstra's, Bellman-Ford, and Floyd-Warshall Algorithms: Key Differences and Python Implementations

Dijkstra's algorithm excels for single-source shortest paths with non-negative weights in sparse graphs, Bellman-Ford handles negative edges and detects negative cycles for single-source problems, and Floyd-Warshall computes all-pairs shortest paths using dynamic programming for dense graphs.

Choosing the right shortest-path algorithm depends on your graph's edge weights, density, and whether you need distances from one source or between every pair of vertices. The TheAlgorithms/Python repository provides clean, educational implementations of all three algorithms in the graphs/ directory, making it easy to compare their practical differences.

Algorithm Overview and Key Characteristics

Dijkstra's Algorithm: Single-Source with Non-Negative Weights

Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights. As implemented in graphs/dijkstra_algorithm.py, the Graph class uses a custom PriorityQueue (min-heap) to greedily select the unvisited node with the smallest tentative distance.

The algorithm guarantees optimal results because once a vertex is extracted from the heap, its shortest distance is finalized. However, negative edges break this guarantee—Dijkstra's may produce incorrect results if negative weights exist because it never revisits finalized nodes.

Bellman-Ford Algorithm: Handling Negative Edges and Cycle Detection

Bellman-Ford also solves the single-source shortest path problem but relaxes the non-negative constraint. The implementation in graphs/bellman_ford.py accepts graphs with negative edge weights and explicitly detects negative-weight cycles that would make shortest paths undefined.

The algorithm works by relaxing all edges V-1 times (where V is the vertex count), followed by an additional pass to check for negative cycles. If any distance can still be reduced, a negative cycle exists and the function raises an exception. This robustness comes at a higher computational cost than Dijkstra's.

Floyd-Warshall Algorithm: All-Pairs Shortest Paths

Floyd-Warshall takes a fundamentally different approach, solving the all-pairs shortest path problem using dynamic programming. The implementation in graphs/graphs_floyd_warshall.py computes shortest distances between every pair of vertices simultaneously.

The algorithm iteratively improves shortest paths by considering each vertex as a potential intermediate point. It handles negative edge weights but does not detect negative cycles—if one exists, the results will be incorrect without warning. Floyd-Warshall is ideal when you need a complete distance matrix for dense graphs or frequent path queries between arbitrary nodes.

Time and Space Complexity Comparison

Understanding the computational trade-offs helps select the right algorithm for your data scale:

Algorithm	Time Complexity	Space Complexity	Best For
Dijkstra (min-heap)	O((V + E) log V)	O(V + E)	Large sparse graphs with non-negative weights
Bellman-Ford	O(V · E)	O(V + E)	Graphs with negative edges; cycle detection required
Floyd-Warshall	O(V³)	O(V²)	Dense graphs; all-pairs distance matrix needed

Dijkstra's logarithmic factor makes it the fastest for sparse graphs like road networks. Bellman-Ford's linear dependency on edges suits smaller graphs where negative weights exist. Floyd-Warshall's cubic time is acceptable only for dense graphs or when you need constant-time lookups between any two nodes after preprocessing.

When to Use Each Algorithm

Use Dijkstra's Algorithm When:

• All edge weights are non-negative (road distances, time costs)
• You need shortest paths from one source to all other nodes
• Working with large, sparse graphs where E << V²
• Real-time performance is critical (GPS navigation, game pathfinding)

Use Bellman-Ford Algorithm When:

• Edge weights may be negative (financial arbitrage, profit/loss scenarios)
• You need to detect negative-weight cycles that invalidate shortest paths
• The graph is small to moderate in size (highway tolls with discounts)
• You only need single-source results but require robustness against negative data

Use Floyd-Warshall Algorithm When:

• You need shortest paths between all pairs of vertices (network latency tables)
• The graph is dense or moderately sized (typically V < 500-1000)
• You want constant-time queries after preprocessing (dynamic programming table lookup)
• Transitive closure or reachability analysis is required (path existence, not just distance)

Implementation Examples from TheAlgorithms/Python

Dijkstra's Implementation

The graphs/dijkstra_algorithm.py file implements Dijkstra's using an adjacency list and custom PriorityQueue:

from graphs.dijkstra_algorithm import Graph

# Create graph with 5 vertices

g = Graph(5)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 1)
g.add_edge(1, 3, 1)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 5)
g.add_edge(3, 4, 3)

# Compute shortest paths from source 0

g.dijkstra(src=0)
g.show_path(0, 4)  # Output: 0 -> 2 -> 1 -> 3 -> 4

The dijkstra() method uses a min-heap to achieve O((V+E) log V) complexity, finalizing each node's distance upon extraction from the priority queue.

Bellman-Ford Implementation

The graphs/bellman_ford.py file provides a function that handles negative edges and detects cycles:

from graphs.bellman_ford import bellman_ford

# Edge list representation with a negative weight

edges = [
    {"src": 0, "dst": 1, "weight": 5},
    {"src": 1, "dst": 2, "weight": -2},
    {"src": 2, "dst": 3, "weight": 3},
    {"src": 3, "dst": 1, "weight": 1}  # Creates cycle with positive weight

]

# Compute distances from source 0

distances = bellman_ford(edges, vertex_count=4, edge_count=4, src=0)
print(distances)  # -> [0.0, 5.0, 3.0, 6.0]

The implementation relaxes all edges V-1 times, then performs an additional pass to check for negative cycles, raising an exception if detected.

Floyd-Warshall Implementation

The graphs/graphs_floyd_warshall.py file implements the dynamic programming approach for all-pairs shortest paths:

from graphs.graphs_floyd_warshall import floyd_warshall

INF = float('inf')

# Adjacency matrix representation

graph = [
    [0,   3, INF,   7],
    [8,   0,   2, INF],
    [5, INF,   0,   1],
    [2, INF, INF,   0],
]

dist_matrix, _ = floyd_warshall(graph, v=4)

# Result: shortest distance between every pair of vertices

print(dist_matrix[0][3])  # -> 6 (path: 0->1->2->3 or 0->3 directly is 7, but 0->1->2->3 = 3+2+1=6)

This implementation uses three nested loops to iteratively improve paths through intermediate vertices, returning a complete distance matrix suitable for constant-time lookups.

Summary

• Dijkstra's algorithm (graphs/dijkstra_algorithm.py) provides the fastest single-source solution for graphs with non-negative weights, using a min-heap priority queue to achieve O((V+E) log V) time complexity.

• Bellman-Ford algorithm (graphs/bellman_ford.py) handles negative edge weights and detects negative-weight cycles through V-1 relaxation passes plus a validation step, making it essential for financial modeling and arbitrage detection despite its O(V·E) complexity.

• Floyd-Warshall algorithm (graphs/graphs_floyd_warshall.py) computes all-pairs shortest paths using dynamic programming in O(V³) time and O(V²) space, ideal for dense networks requiring constant-time distance queries between arbitrary vertices.

Choose Dijkstra's for speed on large sparse graphs with positive weights, Bellman-Ford when negative edges or cycle detection is required, and Floyd-Warshall when you need a complete distance matrix for all vertex pairs.

Frequently Asked Questions

Can Dijkstra's algorithm handle negative edge weights?

No, Dijkstra's algorithm cannot handle negative edge weights. The algorithm assumes that once a vertex is extracted from the priority queue, its shortest distance is finalized. Negative edges can violate this assumption by providing a shorter path to an already-finalized vertex through a different route. For graphs with negative weights, use the Bellman-Ford algorithm implemented in graphs/bellman_ford.py.

How does Bellman-Ford detect negative cycles?

Bellman-Ford detects negative cycles by performing one additional relaxation pass after the standard V-1 iterations. If any distance can be reduced during this extra pass, a negative-weight cycle exists that can be traversed indefinitely to decrease path cost. The implementation in graphs/bellman_ford.py raises an exception when such a cycle is detected, preventing the return of invalid shortest paths.

When should I choose Floyd-Warshall over running Dijkstra or Bellman-Ford multiple times?

Choose Floyd-Warshall when you need shortest paths between all pairs of vertices and the graph is dense or moderately sized (typically fewer than 500-1000 vertices). Running Dijkstra's algorithm from every source would cost O(V·(V+E) log V), which exceeds Floyd-Warshall's O(V³) when E approaches V². Additionally, Floyd-Warshall handles negative edges (without cycle detection) and provides constant-time O(1) distance lookups after the initial computation, making it ideal for network latency tables and transitive closure operations.

What is the space complexity difference between these three algorithms?

Dijkstra's and Bellman-Ford both require O(V + E) space, storing adjacency lists and distance arrays. Dijkstra's adds O(V) for the priority queue, while Bellman-Ford stores the edge list explicitly. Floyd-Warshall requires O(V²) space to store the distance matrix for all pairs, making it more memory-intensive for large graphs but necessary for all-pairs queries.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}