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!

Cheers Rolf

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.

In reply to Re^3: Short Circuiting DFS Graph Traversal by LanX
in thread Short Circuiting DFS Graph Traversal by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.