Bellman-Ford
Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.
Time complexity O(V·E), gograph function path.BellmanFord.
School run
Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.
A directed, weighted graph with 6 vertices and 13 edges.
How many minutes is the quickest drive from home to each place, including the school?
Use it in Go
dist, err := path.BellmanFord(g, "Home")
if err != nil {
return err // path.ErrNegativeWeightCycle
}
fmt.Println(dist["School"])Example graphs
- School run, 6 vertices and 13 edges
- Major currencies, 6 vertices and 20 edges
- Delivery area, 8 vertices and 12 edges
- Arbitrage loop, 8 vertices and 24 edges
- One-way city, 45 vertices and 88 edges
More in Shortest paths
- Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
- Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.