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.
Time complexity O(V³), gograph function path.FloydWarshall.
How it works
Floyd-Warshall fills a table with a distance for every pair of vertices: the edge's weight where there is an edge, 0 from a vertex to itself, and infinity everywhere else. Then it takes each vertex in turn as a stop on the way. For every pair, if going through that stop is shorter than the distance in the table, the table takes the shorter one. After the last vertex, each entry is the shortest distance by any route.
It allows negative weights. A vertex that ends with a negative distance to itself is on a negative cycle, and path.FloydWarshall returns ErrNegativeWeightCycle. It needs a directed, weighted graph.
Three loops over the vertices make it O(V³) in time and O(V²) in memory, whatever the number of edges. It suits small or dense graphs where you want every distance at once, such as a table of travel times between all the stops of a route. On a large graph with few edges, running Dijkstra from each vertex costs less.
Downtown grid
Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.
A directed, weighted graph with 20 vertices and 60 edges.
How many minutes is the quickest drive between every pair of intersections, with Market closed between 2nd and 3rd?
All 380 pairs of different vertices have a path. The longest of the shortest distances is 17, from Pine & 5th to River & 1st.
Step by step
- Each distance starts as the weight of the edge from one vertex to the other, ∞ where there is no edge, and 0 from a vertex to itself. Floyd-Warshall then runs 20 rounds, one per vertex, and each round lets paths stop at one more vertex.
- Round 1 of 20: paths may now go through Pine & 1st. 2 pairs that had no path get one.
- Pine & 2nd to Main & 1st through Pine & 1st: 2 + 2 = 4, so the distance becomes 4.
- Main & 1st to Pine & 2nd through Pine & 1st: 2 + 2 = 4, so the distance becomes 4.
- Round 2 of 20: paths may now go through Pine & 2nd. 8 pairs that had no path get one.
- Pine & 1st to Pine & 3rd through Pine & 2nd: 2 + 3 = 5, so the distance becomes 5.
563 more steps lead to the last one:
- Done. No vertex has a distance below 0 to itself, and no edge gives a shorter distance, so there is no negative cycle. Every distance is final.
Use it in Go
dist, err := path.FloydWarshall(g)
if err != nil {
return err
}
fmt.Println(dist["Pine & 1st"]["River & 5th"])
fmt.Println(dist["River & 5th"]["Pine & 1st"]) // +Inf when there is no path
Example graphs
- Major currencies, 6 vertices and 20 edges
- Delivery area, 8 vertices and 12 edges
- Downtown grid, 20 vertices and 60 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.
- 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.