# Dijkstra's Algorithm vs Bellman-Ford: Key Differences for Shortest-Path Computation

> Dijkstra's and Bellman-Ford algorithms find shortest paths. Discover their key differences in complexity and handling negative edge weights to choose the right algorithm.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**Dijkstra's algorithm uses a min-priority queue to achieve O((V + E) log V) time complexity but only works with non-negative edge weights, while Bellman-Ford iterates over all edges V-1 times to handle negative weights at O(V·E) complexity.**

Both algorithms solve the single-source shortest-path problem in the `trekhleb/javascript-algorithms` repository, yet they differ fundamentally in data structures, performance characteristics, and edge-case handling. Understanding these distinctions is crucial for selecting the right algorithm for your graph's specific constraints.

## Core Architectural Differences

### Data Structures and Vertex Selection

**Dijkstra's algorithm** relies on a **min-priority queue** (binary heap) to always extract the vertex with the smallest tentative distance. In [`src/algorithms/graph/dijkstra/dijkstra.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/dijkstra/dijkstra.js), the priority queue initialization occurs at lines 33-34, and the algorithm maintains a `visitedVertices` set (lines 16-20) to track processed nodes. When a shorter path is discovered, the implementation updates priorities (lines 55-57) and inserts undiscovered neighbors (lines 63-66).

**Bellman-Ford** eliminates complex queue management entirely. The implementation in [`src/algorithms/graph/bellman-ford/bellmanFord.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/bellman-ford/bellmanFord.js) uses simple iteration over all vertices, running the outer loop `|V|-1` times (line 21). This design trades efficiency for flexibility, requiring only distance and predecessor maps (lines 7-9) without tracking visited states.

### Edge Weight Constraints

The most critical distinction lies in **negative edge weight handling**. Dijkstra assumes strictly non-negative weights; encountering a negative weight after marking a vertex visited (line 71 in the source) produces incorrect results because the algorithm never revisits settled nodes. Conversely, Bellman-Ford relaxes every edge on each iteration (lines 26-37), allowing distances to improve throughout all passes regardless of sign.

## Complexity and Performance Analysis

| Metric | Dijkstra | Bellman-Ford |
|--------|----------|--------------|
| **Time Complexity** | O((V + E) log V) | O(V · E) |
| **Space Complexity** | O(V + E) | O(V) |
| **Early Termination** | Yes, when priority queue empties | No, always completes \|V\|-1 passes |
| **Negative Cycle Detection** | Not supported | Possible (though not implemented in this version) |

Dijkstra's logarithmic time factor stems from heap operations, making it superior for large, sparse graphs like road networks. Bellman-Ford's quadratic behavior becomes prohibitive for dense graphs but remains necessary when negative edges exist.

## Implementation Deep Dive

### Dijkstra's Priority Queue Approach

The Dijkstra implementation initializes `distances` and `previousVertices` maps alongside a `PriorityQueue` instance (lines 16-20). The core loop extracts the minimum vertex, then examines neighbors only if unvisited (line 43). Distance improvements trigger priority updates (lines 50-61), ensuring the heap always contains the current best known distances. The method returns an object containing `distances` and `previousVertices` (lines 74-80).

### Bellman-Ford's Relaxation Strategy

Bellman-Ford prepares identical result structures (lines 7-9) but sets the start vertex distance to 0 (line 12) before entering the relaxation loop. Unlike Dijkstra's selective neighbor examination, this algorithm iterates through every edge in the graph during each of the `|V|-1` passes. The repository's version returns the same shape as Dijkstra (lines 41-44), though classic implementations often add a final cycle-detection pass.

## Handling Negative Weights: A Practical Example

Consider a directed graph where vertex A connects to B (weight 4), A connects to C (weight 2), and B connects to C (weight -3). Only Bellman-Ford can compute the correct shortest path from A to C through B.

```javascript
import Graph from '../../data-structures/graph/Graph';
import dijkstra from '../../algorithms/graph/dijkstra/dijkstra';
import bellmanFord from '../../algorithms/graph/bellman-ford/bellmanFord';

// Build a weighted directed graph
const graph = new Graph(true);
const A = graph.addVertex('A');
const B = graph.addVertex('B');
const C = graph.addVertex('C');

graph.addEdge(A, B, 4);   // weight 4
graph.addEdge(A, C, 2);   // weight 2
graph.addEdge(B, C, -3);  // negative weight (only Bellman-Ford handles correctly)

// Dijkstra fails on negative weights
try {
  const { distances } = dijkstra(graph, A);
  console.log('Dijkstra distances:', distances); // Potentially incorrect
} catch (e) {
  console.error('Dijkstra cannot process negative edges.');
}

// Bellman-Ford correctly finds A->B->C with total weight 1
const { distances } = bellmanFord(graph, A);
console.log('Bellman-Ford distances:', distances);

```

Running this snippet demonstrates Bellman-Ford's ability to process the negative edge from B to C, yielding a total distance of 1 from A to C, while Dijkstra produces undefined or incorrect behavior.

## Summary

- **Dijkstra's algorithm** requires [`src/data-structures/priority-queue/PriorityQueue.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/priority-queue/PriorityQueue.js) for O((V + E) log V) performance but fails with negative edge weights.
- **Bellman-Ford** uses simple iteration in [`src/algorithms/graph/bellman-ford/bellmanFord.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/bellman-ford/bellmanFord.js) to support negative weights at O(V·E) complexity.
- Both return identical result structures containing `distances` and `previousVertices` maps.
- Choose Dijkstra for large, non-negative weighted graphs; use Bellman-Ford when negative edges or cycle detection is required.

## Frequently Asked Questions

### Can Dijkstra's algorithm handle negative edge weights?

No. Dijkstra's algorithm assumes non-negative edge weights because once a vertex is marked visited (line 71 in [`dijkstra.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/dijkstra.js)), its distance is considered final. Negative weights appearing later in the graph could create shorter paths through already-visited vertices, which the algorithm never revisits, resulting in incorrect shortest-path calculations.

### Why is Bellman-Ford slower than Dijkstra?

Bellman-Ford runs in O(V·E) time because it performs `|V|-1` relaxation passes over every edge in the graph, regardless of whether distances have converged. Dijkstra achieves O((V + E) log V) by using a min-heap to process each vertex only once, skipping edges to already-settled nodes. This difference makes Bellman-Ford significantly slower on dense graphs but necessary for negative weight scenarios.

### Which algorithm should I use for road network routing?

Use **Dijkstra's algorithm** for road networks, as physical road distances are inherently non-negative. The priority queue implementation in [`src/algorithms/graph/dijkstra/dijkstra.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/dijkstra/dijkstra.js) provides superior performance for sparse graphs typical of geographic routing, while Bellman-Ford's O(V·E) complexity would introduce unnecessary computational overhead.

### Does the trekhleb implementation detect negative cycles?

The current implementation in [`src/algorithms/graph/bellman-ford/bellmanFord.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/bellman-ford/bellmanFord.js) does not include the final verification pass to detect negative cycles, though the classic Bellman-Ford algorithm can be extended to do so. To detect negative cycles, you would need to add an additional iteration after the `|V|-1` passes to check if any distance can still be improved, indicating a reachable negative-weight cycle.