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.

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 between every pair of stops, so a route can start anywhere, not just at the depot?

23 of the 56 pairs of different vertices have a path. The longest of the shortest distances is 14, from Depot to Station.

Step by step

  1. 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 8 rounds, one per vertex, and each round lets paths stop at one more vertex.
  2. Round 1 of 8: paths may now go through Depot. No distance gets shorter.
  3. Round 2 of 8: paths may now go through Bakery. 3 pairs that had no path get one.
  4. Depot to School through Bakery: 4 + 5 = 9, so the distance becomes 9.
  5. Depot to Park through Bakery: 4 + 7 = 11, so the distance becomes 11.
  6. Market to School through Bakery: 1 + 5 = 6, so the distance becomes 6.

19 more steps lead to the last one:

  1. 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. 33 pairs have no path, so their distances stay ∞.

Use it in Go

dist, err := path.FloydWarshall(g)
if err != nil {
	return err
}
fmt.Println(dist["Depot"]["Station"])
fmt.Println(dist["Station"]["Depot"]) // +Inf when there is no path

Example graphs

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.

All algorithms