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