I'm not sure if I'm getting you right because your example confuses me.

I suppose what you mean is

  A---F
 /|\ /      
0 | C    H -1
 \|/ \  /
  B   G

[download]

For any path from 0 to C that includes A it's useless to continue to F.¹

This situation reminds me of the Max-flow min-cut theorem.

IMHO finding all pathes is related to maximizing the flow and the set {C} is a min-cut.

I.a.w. any path from 0 to 1 will be a combination of paths from 0-C and C-1. ²

I'm sure this kind of problem is already extensively investigated in literature.

BTW my initial idea to improve my solution is to start from both ends but I'm reluctant to improve solutions for loosely expressed problems, (normally that results in launching rockets where throwing a stone is efficient and optimal).

Cheers Rolf

UPDATES:

1) i.e. after 0-A-C, 0-B-A-C, 0-A-B-C don't continue to F

2) partitioning into separated subgraphs allows a divide and conquer approach.

In reply to Re: 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.