gonum/graph — pull request #6 by Jragonmiris (2014-02-06 09:29:30+00:00)
Title: Added FloydWarshall

I added an implementation of Floyd-Warshall. Its returns are a little different from the usual. Since with FW it's easy to keep track of which nodes are valid shortest-path successors, it returns two functions: one that returns a single path between start and goal, and one that returns all possible paths between start and goal.

I'm actually rather fond of this method of dealing with functions that have to return multiple paths, and may consider switching Johnson's, Dijkstra's, etc to returning a PathFunc instead of a couple giant maps of path and cost information

The function is tested, but there's always room for more. I'm 99% certain that all my Floyd-Warshall logic and my recursive logic for building paths is correct. Most of my errors were just from double-counting or not counting nodes that were traversed due to the way the recursive function adds to the path slice, so you'd get paths like [1,2,2,5] instead of [1,2,5]. It should all be fixed and tested for now, but if anyone can think of an edge case I didn't test adding it would be nice.

There are apparently some uses for this in fields like dynamic network load balancing (find all router chains that get to the target equally quickly under no stress, and choose the one with the least load).

But, honestly, mostly I added it since we now have a tested method of generating all shortest paths between A and B, and thus we can test Dijkstra, A*, and everything else against it by asking "does the shortest path you find match ANY of the possible shortest paths" instead of doing guess-and-check test generation. It only works on 0-indexed dense graphs, but it should be fine.