BellmanFord

Bellman-Ford shortest-path algorithm supporting negative edge weights.

Unlike Dijkstra, Bellman-Ford can handle negative edge weights. It works by relaxing all edges |V| − 1 times, then performing one final relaxation pass to detect negative-weight cycles (cycles where the total weight is less than zero). If such a cycle exists, no well-defined shortest path can be computed for vertices reachable through it.

When to use each algorithm

Scenario	Algorithm
All weights ≥ 0, single target	Dijkstra.shortestPath
All weights ≥ 0, weighted traversal	Dijkstra.toIterator
All weights ≥ 0, heuristic available	AStar.shortestPath
Negative weights possible	BellmanFord

allVertices parameter

Bellman-Ford needs to enumerate every edge in the graph, which requires knowing every vertex. Pass the complete list as allVertices: { V }. Vertices reachable from start that are not in allVertices are treated as unreachable.

All functions accept either callback form for GetNeighbors — see GraphUtil for details.

Example

--        1         3
--  A ──→ B ──────→ D
--        │
--       -2
--        ↓
--        C

local weights = {
    A = { B = 1 },
    B = { C = -2, D = 3 },
    C = {},
    D = {},
}
local allVertices = { "A", "B", "C", "D" }

local function getNeighbors(v) return ... end
local function getWeight(from, to) return weights[from][to] end

local path, hasNegativeCycle = BellmanFord.shortestPath("A", "C", allVertices, getNeighbors, getWeight)
-- path.path  == { "A", "B", "C" }
-- path.cost  == -1   (1 + -2)
-- hasNegativeCycle == false

Functions

shortestPath

directedundirected

</>

BellmanFord.shortestPath(

start: V,

goal: V,

allVertices: {V},

getNeighbors: GetNeighbors<V>,

getWeight: GetWeight<V>

) → (

PathResult<V>?,

boolean

)

Finds the shortest weighted path from start to goal, returning a (PathResult<V>?, boolean) tuple.

• First return — a PathResult if a path exists and no negative cycle was detected; nil otherwise.
• Second return — true if a negative-weight cycle was detected in the reachable subgraph from start (in which case the first return is always nil).

local result, hasNegCycle = BellmanFord.shortestPath(
    "A", "C", allVertices, getNeighbors, getWeight
)
if hasNegCycle then
    warn("Graph contains a negative-weight cycle")
elseif result == nil then
    warn("Goal is unreachable")
else
    print("Cost:", result.cost)
end

Time complexity: O(V · E)

distances

directedundirected

</>

BellmanFord.distances(

start: V,

allVertices: {V},

getNeighbors: GetNeighbors<V>,

getWeight: GetWeight<V>

) → (

{[V]: number},

boolean

)

Runs Bellman-Ford from start and returns all shortest distances from start to every vertex in allVertices, alongside a negative-cycle flag.

• First return — { [V]: number } mapping each reachable vertex to its shortest distance from start. Vertices in allVertices that are unreachable have a value of math.huge.
• Second return — true if a negative-weight cycle was detected. Distances may be incorrect for vertices affected by the cycle.

local distances, hasNegCycle = BellmanFord.distances("A", allVertices, getNeighbors, getWeight)
if not hasNegCycle then
    print(distances["D"]) -- shortest dist A→D
end

Time complexity: O(V · E)