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

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, 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 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.

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 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 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), 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 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 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.

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