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

> Compare Dijkstra's Bellman-Ford and Floyd-Warshall. Learn their differences use cases and Python implementations for shortest path problems with non-negative or negative weights and all-pairs paths.

- Repository: [The Algorithms/Python](https://github.com/TheAlgorithms/Python)
- Tags: deep-dive
- Published: 2026-02-24

---

**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](https://github.com/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/graphs/dijkstra_algorithm.py) file implements Dijkstra's using an adjacency list and custom `PriorityQueue`:

```python
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`](https://github.com/TheAlgorithms/Python/blob/main/graphs/bellman_ford.py) file provides a function that handles negative edges and detects cycles:

```python
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`](https://github.com/TheAlgorithms/Python/blob/main/graphs/graphs_floyd_warshall.py) file implements the dynamic programming approach for all-pairs shortest paths:

```python
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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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.