Edge weights #4: shortest path(s)

[mtorpey]

This adds algorithms for finding shortest paths in edge-weighted digraphs, where "shortest" means "lowest total weight".

Three different "shortest path" problems are solved:

• All pairs: DigraphShortestPaths(digraph)
• Single source: DigraphShortestPaths(digraph, source)
• Source and destination: DigraphShortestPath (digraph, source, dest)

The "all pairs" problem has two algorithms:

• Johnson: better for sparse digraphs
• Floyd–Warshall: better for dense graphs

The "single source" problem has three algorithms:

• If "all pairs" is already known, extract information for the given source
• Dijkstra: faster, but cannot handle negative weights
• Bellman–Ford: slower, but handles negative weights

The "source and destination" problem calls the "single source" problem and extracts information for the given destination.

Justification and benchmarks are in @RaiyanC's MSci thesis, Chapter 6.

[mtorpey]

Is there a reason not to use the existing implementation [of Floyd–Warshall]? Iirc the existing implementation is pretty flexible.

I've taken a look at FLOYD_WARSHALL in digraphs.c, and it would need quite a lot of reworking to use here, for 2 reasons:

• It always creates a distance matrix consisting of two values (edge and non-edge) rather than multiple values
• It only stores distances, and doesn't remember info about the actual paths.

Obviously we could refactor the C code, but perhaps that's a future issue?

[markuspf]

Small nitpick about the "source-destination" solution:

At the moment (as documented) this calls the single-source solution and extracts the information from that; this is in many cases way less efficient than exiting early once the destination is found;

This is easy to fix and shouldn't be a blocker for this PR. Just leaving this here as it will pop back up when #570 as I purposefully implemented Dijkstra with source and destination and single source for exactly that reason.