@graphty/algorithms / index / bellmanFord
Function: bellmanFord() ​
bellmanFord(
g,sourceNode,options?):BellmanFordResult
Defined in: indexed/bellman-ford.ts:34
Bellman-Ford single-source shortest paths, index-based, for weights that may be negative. It relaxes every arc, so an undirected edge is relaxed both ways (it has an arc in each direction), and one negative undirected edge is therefore a negative cycle. Rounds stop early once one changes nothing; after nodeCount - 1 rounds one more round decides hasNegativeCycle. The predecessor is the relaxing ARC, as in dijkstra, so a parallel edge on a path is identified exactly.
Parameters ​
g ​
AdjacencyView
The adjacency to search
sourceNode ​
NodeRef
The node to start from: its index, or { id }
options? ​
SsspOptions = {}
Cutoff (a relaxation beyond it is skipped) and per-arc weight override
Returns ​
The distances, the predecessor arcs, the path accessors and the negative-cycle flag