The shortest path can be found by inspecting the vector p. But my goal is slightly different.
Does anyone know how to "record" all shortest paths between two vertices? (i.e. all paths having the minimal path length)
I coded up something like this a couple of years ago. My approach was to keep running a shortest paths algorithm until I ran out of paths. The tricky part is that you have to invalidate each shortest path as you go. I did this by using a color map for edges. White means a viable edge, black means you've already used it and can't re-cross it. This approach isn't actually correct and you can prove that it won't find all shortest paths with a fairly simple counterexample. It might be made correct if you associate a path with each vector (or edge?) and disallow traversals based on more that information rather than a simple white/black coloring. The naive approach might be a good place to start. Andrew