I’m writing a graph package, and for testing shortest path algorithms, I thought it may be useful to have an algorithm that generates all possible shortest paths between two vertices in a weighted, directed graph. That way I would only have to hand-solve toy cases to test this algorithm, then I could use that algorithm to generate sets of possible answers for all the other ones. Multiple optimal paths frequently exist, and most shortest path algorithms find only one and which one they find is based on the successor function ordering and priority queue sorting and phase of the moon and the current disposition of Fenris and all sorts of other hard to control stuff.

It looks like Matlab may have a function in a standard library that does this, which of course doesn’t have any open source code I can look at, but I haven’t found any standard algorithms or pseudocode. I could probably devise one (probably by modifying Uniform Cost Search), but there’s no point reinventing the wheel if I don’t have to.

I understand that the running time for such an algorithm is almost necessarily going to be bonkers, but it’s not a big deal since it probably won’t be used on very large graphs, and is unlikely to be used except in testing, which doesn’t have to be blazing fast. At worst, I can run it once, save the output to disk, and then compare against that instead of running it every time. (I mean, in cases that take a while but not “multiple months to find the solution” a while).