Safe Haskell	None
Language	GHC2021

Data.Graph.BellmanFord

Synopsis

type Vertex = Int
bellmanFord :: Int -> Vertex -> Vector (Vertex, Vertex, Int) -> Vector Int

Documentation

type Vertex = Int Source #

bellmanFord :: Int -> Vertex -> Vector (Vertex, Vertex, Int) -> Vector Int Source #

Bellman-Ford O(VE)

dist[v] == maxBound iff v is unreachable

dist[v] == minBound iff v in negative cycle

>>> bellmanFord 2 0 (U.singleton (0, 1, -1))
[0,-1]
>>> bellmanFord 2 0 U.empty
[0,9223372036854775807]
>>> bellmanFord 1 0 (U.singleton (0, 0, -1))
[-9223372036854775808]
>>> bellmanFord 2 0 (U.fromList [(0, 1, -1), (1, 0, -1)])
[-9223372036854775808,-9223372036854775808]