bellman_ford

Bellman-Ford algorithm for finding shortest paths in graphs with negative edge weights.

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

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),
  add: fn(e, e) -> e,
  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

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.

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,
  add: fn(e, e) -> e,
  compare: fn(e, e) -> order.Order,
) -> #(dict.Dict(Int, e), dict.Dict(Int, Int))