BellmanFord (yog-fsharp)

BellmanFord Module

Namespace: Yog.Pathfinding
Assembly: Yog.FSharp.dll

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	bellmanFord	O(VE)	Negative weights, cycle detection
SPFA (Queue-optimized)	implicitBellmanFord	O(E) average	Sparse graphs with few negative edges

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

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.

Types

Type	Description
BellmanFordResult<'e>	Result type for Bellman-Ford algorithm.
ImplicitBellmanFordResult<'cost>	Result type for implicit Bellman-Ford algorithm.

Functions and values

Function or value	Description
`bellmanFord zero add compare start goal graph` Full Usage: `bellmanFord zero add compare start goal graph` Parameters: zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `BellmanFordResult<'e>`	Finds shortest path with support for negative edge weights using Bellman-Ford. Time Complexity: O(VE) zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `BellmanFordResult<'e>`
`bellmanFordFloat start goal graph` Full Usage: `bellmanFordFloat start goal graph` Parameters: start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `BellmanFordResult<float>`	Finds shortest path with float weights, handling negative edges. start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `BellmanFordResult<float>`
`bellmanFordInt start goal graph` Full Usage: `bellmanFordInt start goal graph` Parameters: start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `BellmanFordResult<int>`	Finds shortest path with integer weights, handling negative edges. start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `BellmanFordResult<int>`
`implicitBellmanFord zero add compare successors isGoal start` Full Usage: `implicitBellmanFord zero add compare successors isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `ImplicitBellmanFordResult<'cost>`	Finds shortest path in implicit graphs with support for negative edge weights. Uses SPFA (Shortest Path Faster Algorithm) internally. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `ImplicitBellmanFordResult<'cost>`
`implicitBellmanFordBy zero add compare successors keyFn isGoal start` Full Usage: `implicitBellmanFordBy zero add compare successors keyFn isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `ImplicitBellmanFordResult<'cost>`	Like `implicitBellmanFord`, but deduplicates visited states by a custom key. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `ImplicitBellmanFordResult<'cost>`