bellman_ford

Bellman-Ford algorithm for single-source shortest paths with support for negative edge weights.

The Bellman-Ford algorithm finds shortest paths from a source node to all other nodes, even when edges have negative weights. It can also detect negative cycles reachable from the source, which make shortest paths undefined.

Algorithm

Algorithm	Function	Complexity	Best For
Bellman-Ford	`bellman_ford/6`	O(VE)	Negative weights, cycle detection
SPFA (Queue-optimized)	`bellman_ford/6`	O(E) average	Sparse graphs with few negative edges
Implicit Bellman-Ford	`implicit_bellman_ford/6`	O(VE)	Implicit/large graphs

Key Concepts

Relaxation: Repeatedly improve distance estimates (V-1 passes)
Negative Cycle: Cycle with total negative weight (no shortest path exists)
Shortest Path Tree: Tree of shortest paths from source to all nodes

Why V-1 Relaxation Passes?

In a graph with V nodes, any shortest path has at most V-1 edges. Each pass of Bellman-Ford relaxes all edges, propagating shortest path information one hop further each time.

Comparison with Dijkstra

Feature	Bellman-Ford	Dijkstra
Negative weights	✅ Yes	❌ No
Negative cycle detection	✅ Yes	❌ N/A
Time complexity	O(VE)	O((V+E) log V)
Data structure	Simple loops	Priority queue

When to Use Bellman-Ford

Use Bellman-Ford when:

Edge weights may be negative
You need to detect negative cycles
The graph is small or sparse enough for O(VE)

Use Dijkstra when:

All edge weights are non-negative
You need better performance

Use Cases

Currency arbitrage: Detecting negative cycles in exchange rates
Financial modeling: Cost calculations with credits/penalties
Chemical reactions: Energy changes with positive and negative values
Constraint solving: Difference constraints systems

History

Published independently by Richard Bellman (1958) and Lester Ford Jr. (1956). The algorithm is a classic example of dynamic programming.

References

Types

BellmanFordResult

</>

Result type for Bellman-Ford algorithm.

pub type BellmanFordResult(e) {
  ShortestPath(path: utils.Path(e))
  NegativeCycle
  NoPath
}

Constructors

```
ShortestPath(path: utils.Path(e))
```
A shortest path was found successfully
```
NegativeCycle
```
A negative cycle was detected (reachable from source)
```
NoPath
```
No path exists from start to goal

ImplicitBellmanFordResult

</>

Result type for implicit Bellman-Ford algorithm.

pub type ImplicitBellmanFordResult(cost) {
  FoundGoal(cost)
  DetectedNegativeCycle
  NoGoal
}

Constructors

```
FoundGoal(cost)
```
A shortest distance to goal was found
```
DetectedNegativeCycle
```
A negative cycle was detected (reachable from start)
```
NoGoal
```
No goal state was reached

Values

bellman_ford

</>

pub fn bellman_ford(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> BellmanFordResult(e)

Finds shortest path with support for negative edge weights using Bellman-Ford.

Time Complexity: O(VE)

Returns

ShortestPath(path): If a valid shortest path exists
NegativeCycle: If a negative cycle is reachable from the start node
NoPath: If no path exists from start to goal

Parameters

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two weights
compare: Function to compare two weights

bellman_ford_float

</>

pub fn bellman_ford_float(
  in graph: model.Graph(n, Float),
  from start: Int,
  to goal: Int,
) -> BellmanFordResult(Float)

Finds shortest path with float weights, handling negative edges.

This is a convenience wrapper around bellman_ford that uses:

0.0 as the zero element
float.add for addition
float.compare for comparison

Warning

Float arithmetic has precision limitations. Negative cycles might not be detected reliably due to floating-point errors. Prefer Int weights for critical calculations.

bellman_ford_int

</>

pub fn bellman_ford_int(
  in graph: model.Graph(n, Int),
  from start: Int,
  to goal: Int,
) -> BellmanFordResult(Int)

Finds shortest path with integer weights, handling negative edges.

This is a convenience wrapper around bellman_ford that uses:

0 as the zero element
int.add for addition
int.compare for comparison

Example

bellman_ford.bellman_ford_int(graph, from: 1, to: 5)
// => ShortestPath(Path([1, 2, 5], 15))

When to Use

Use this for graphs with Int edge weights that may be negative (arbitrage detection, time-dependent costs, etc.). For graphs with only non-negative weights, prefer dijkstra.shortest_path_int which is faster.

has_negative_cycle

</>

pub fn has_negative_cycle(
  graph: model.Graph(n, e),
  nodes: List(Int),
  distances: dict.Dict(Int, e),
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> Bool

implicit_bellman_ford

</>

pub fn implicit_bellman_ford(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  is_goal is_goal: fn(state) -> Bool,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> ImplicitBellmanFordResult(cost)

Finds shortest path in implicit graphs with support for negative edge weights.

Time Complexity: O(VE) average case

Returns

FoundGoal(cost): If a valid shortest path to goal exists
DetectedNegativeCycle: If a negative cycle is reachable from start
NoGoal: If no goal state is reached

Parameters

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two costs
compare: Function to compare two costs

implicit_bellman_ford_by

</>

pub fn implicit_bellman_ford_by(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  visited_by key_fn: fn(state) -> key,
  is_goal is_goal: fn(state) -> Bool,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> ImplicitBellmanFordResult(cost)

Like implicit_bellman_ford, but deduplicates visited states by a custom key.

Essential when your state carries extra data beyond what defines identity. The visited_by function extracts the deduplication key from each state.

Time Complexity: O(VE) where V and E are measured in unique keys

reconstruct_path

</>

pub fn reconstruct_path(
  predecessors: dict.Dict(Int, Int),
  start: Int,
  current: Int,
  acc: List(Int),
) -> Result(List(Int), Nil)

relaxation_passes

</>

pub fn relaxation_passes(
  graph: model.Graph(n, e),
  nodes: List(Int),
  distances: dict.Dict(Int, e),
  predecessors: dict.Dict(Int, Int),
  remaining: Int,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> #(dict.Dict(Int, e), dict.Dict(Int, Int))