Hmm what about a three phase approach?

Finding "all paths" by backtracking is so expensive because of the power set of combinations of partial "subpaths"!

That's why nobody is interested to test all combinations in a dead track.

What about identifying the nodes/subpaths which can only be part of a solution in a first phase and later on trying to find all combinations.

Lets say in the first phase we mark each node in your example by the minimal distance from the start. (quite a trivial iterative algorithm of low complexity (IMHO O(n)), I already realized it)

   2    1        B2
 / | \ /  \    / | \
3--2--1---D0--Q1 P3 M*
 \ | /         \ |  |
   2             U2-S3
[download]

In the second phase we have to find all "short" paths by "stepping" down from M simply by always choosing a neighbour of lower degree.

I.e. M-B-Q-D or M-S-U-Q-D.

That means this left branch you wanted to avoid won't be visited again and will not cause any notable complexity.

Now finding "all" paths in a third phase could be done by combining "detours" to the shortest path. e.g. M-B-(P-U)-Q-D.

The latter is rather tricky, alternatively one could also simply try a brute force backtracker like already demonstrated, but much faster because it's restricted to step only thru nodes marked in phase 2!

UPDATE: After some thoughts I have to admit that the process to identify "unreachable" parts of the graph as result of phase 2 is more complicated ... too complicated for a simple post, coz I really can't think of any reasonable application of calculating all(!) paths instead of just only the shortest.