Re: [Boost-users] [Graph] how to find all shortest paths (not just one of them)?

Subject: Re: [Boost-users] [Graph] how to find all shortest paths (not just one of them)?
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2010-11-03 09:42:44

> 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