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.
Major currencies
Six major currencies and the rates a dealer quotes between them. Each edge is a trade, and its weight is minus the natural log of the exchange rate, so the shortest path is the best rate. Dollars buy more francs through EUR than directly. The rates are illustrative and close to market rates, and every loop of trades loses a little to the spread.
A directed, weighted graph with 6 vertices and 20 edges.
What is the best rate between every pair of currencies, trading through other currencies when that pays more?
All 30 pairs of different vertices have a path. At the best rates, 1 CAD buys 109.05 JPY, 0.7274 USD, 0.66122 EUR, 0.61701 CHF and 0.56036 GBP.
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 6 rounds, one per vertex, and each round lets paths stop at one more vertex.
- Round 1 of 6: paths may now go through CAD. 2 pairs that had no path get one.
- GBP to JPY through CAD: -0.5752 - 4.6918 = -5.267, so the distance becomes -5.267: 1 GBP buys 193.83 JPY this way.
- JPY to GBP through CAD: 4.6998 + 0.5792 = 5.279, so the distance becomes 5.279: 1 JPY buys 0.0050975 GBP this way.
- Round 2 of 6: paths may now go through CHF. 2 pairs that had no path get one.
- EUR to JPY through CHF: 0.0692 - 5.1701 = -5.1009, so the distance becomes -5.1009: 1 EUR buys 164.17 JPY this way.
19 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["CAD"]["GBP"])
fmt.Println(dist["GBP"]["CAD"]) // +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.