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.BellmanFordPaths.
path.BellmanFord returns the same distances as a map, without the routes.
How it works
Bellman-Ford starts like Dijkstra, with 0 at the start and infinity everywhere else, but it doesn't take vertices in order of distance. It goes through every edge, and when an edge gives its end a shorter distance, it lowers that distance. It repeats this pass one time fewer than there are vertices. A shortest path that doesn't repeat a vertex has at most that many edges, so after the last pass every distance is final.
Then it makes one more pass. If an edge can still shorten a distance, the start can reach a cycle whose weights add up to less than zero. Such a graph has no shortest path, since each trip around the cycle makes the path shorter, and path.BellmanFordPaths returns ErrNegativeWeightCycle. It needs a directed, weighted graph and costs O(V·E). path.NegativeCycle then returns one such cycle. It searches the whole graph rather than what one start reaches, so on a graph with more than one it can return a cycle other than the one the start runs into.
When there is no negative cycle, Distance and PathTo on the result give each distance and the route there, start first, and report false for a vertex out of reach. Of two routes that are equally short, PathTo returns the one with the fewest edges.
Use it when some weights are negative, such as refunds, rewards or the negative logarithms of exchange rates, where a negative cycle is a chance for arbitrage. When no weight is negative, Dijkstra gives the same distances faster.
One-way city
Forty-five intersections, I1 to I45, where I stands for intersection, numbered row by row from the top left with nine to a row. Most streets are one way, and the outer streets form a clockwise loop. Only the middle row (I19 to I27) and the middle column (I5, I14, I23, I32 and I41) go both ways, and each edge is the travel time in minutes.
A directed, weighted graph with 45 vertices and 88 edges.
How many minutes is the quickest drive from I23 to each intersection, when most streets are one way?
From I23, the shortest distances are 3 to I14, 5 to I22, 5 to I24, 5 to I32, 7 to I13, 7 to I25, 7 to I31, 8 to I5, 8 to I21, 9 to I15 and 34 more. The farthest is I18, at 26.
Step by step
- Every distance starts at ∞, except I23, which is 0. Bellman-Ford checks all 88 edges in each of 44 passes, one fewer than the 45 vertices, then once more to look for a negative cycle.
- Pass 1. I23 to I14: 0 + 3 = 3, so I14's distance becomes 3.
- Pass 1. I23 to I22: 0 + 5 = 5, so I22's distance becomes 5.
- Pass 1. I23 to I24: 0 + 5 = 5, so I24's distance becomes 5.
- Pass 1. I23 to I32: 0 + 5 = 5, so I32's distance becomes 5.
- Pass 1. I24 to I15: 5 + 4 = 9, so I15's distance becomes 9.
86 more steps lead to the last one:
- Extra pass. No edge gives a shorter distance, so there is no negative cycle. Every distance from I23 is final.
Use it in Go
paths, err := path.BellmanFordPaths(g, "I23")
if errors.Is(err, path.ErrNegativeWeightCycle) {
loop, _ := path.NegativeCycle(g)
for _, v := range loop {
fmt.Println(v.Label())
}
return err
}
if err != nil {
return err
}
dist, ok := paths.Distance("I2")
if !ok {
return nil // out of reach
}
route, _ := paths.PathTo("I2")
fmt.Println(dist)
for _, v := range route {
fmt.Println(v.Label())
}
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.
- A*: Finds the quickest route from one vertex to another, looking first where a guess of the time left says the goal is, so it settles far fewer vertices than Dijkstra.
- Bidirectional search: Finds the quickest route from one vertex to another by searching forward from the start and backward from the goal at once, until the two searches meet.
- k shortest paths: Finds the k quickest routes from one vertex to another that don't repeat a vertex, quickest first, the way a navigation app offers a few routes.
- Beam search: Looks for a route from one vertex to another while keeping only the few best partial paths at each step, so its memory and time stay bounded, at the cost of sometimes missing the best route.
- Multi-source Dijkstra: Finds the nearest of several sources for every vertex, and the distance from it, in one search.
- k-center: Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it.
- 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.