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.
Delivery area
Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.
A directed, weighted graph with 8 vertices and 12 edges.
How many minutes is the quickest drive from the depot to each stop?
Use it in Go
dist, err := path.BellmanFord(g, "Depot")
if err != nil {
return err // path.ErrNegativeWeightCycle
}
fmt.Println(dist["Station"])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.