Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^3: Short Circuiting DFS Graph Traversal

by choroba (Cardinal)
on Oct 29, 2010 at 14:54 UTC ( [id://868321] : note . print w/replies, xml ) Need Help??


in reply to Re^2: Short Circuiting DFS Graph Traversal
in thread Short Circuiting DFS Graph Traversal

Can the edge cost be set to zero? :) Then, all the possible paths would be the cheapest.
  • Comment on Re^3: Short Circuiting DFS Graph Traversal

Replies are listed 'Best First'.
Re^4: Short Circuiting DFS Graph Traversal
by Limbic~Region (Chancellor) on Oct 29, 2010 at 15:04 UTC
    choroba,
    Most of what I know about graph theory I have learned here but I don't see why not. On the other hand, what you have just described is an unweighted graph which is stated as a given in my original node. I would be VERY impressed if an algorithm exists that can intuitively know not to follow paths that can lead to dead ends without keeping some sort of a cache of previously followed paths. If they can, then certainly they will be more efficient then what I propose and would love to learn about them.

    Cheers - L~R