The Design of Software (CLOSED)A public forum for discussing the design of software, from the user interface to the code architecture. Now closed. 

The "Design of Software" discussion group has been merged with the main
Joel on Software discussion group.
The archives will remain online indefinitely. 
Hello all!
I need a graph algorithm that finds ALL of the paths from (possibly) multiple sources to (possibly) multiple sinks. I've googled and googled and found many references to shortest paths algorithms (Dijkstra, all pairs shortest paths, A*) but I need all of the paths. Does anyone know of anything like this? I'm in the process of trying to modify some of the shortest path algorithms to remove the "shortest path" restriction. Thanks!
should've paid more attention in my algorithms class Wednesday, June 11, 2008
Sounds a bit like the Travelling Salesman problem: http://en.wikipedia.org/wiki/Travelling_salesman_problem
I agree with the previous 2 posters. You may need to narrow your problem down a little.
Developer #13 Wednesday, June 11, 2008
The second your graph has a loop in it you have an infinite number of solutions situation. When you remove the loop you are pretty much looking at tree traversal.
Brian Wednesday, June 11, 2008
and that is if you write it such that you don't fall into the a>b>a>b and variations there in infinite solution.
Brian Wednesday, June 11, 2008
I think you want Warshall's algorithm.
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm If you skip down to the part about Applications & Generalizations, it explains how to do Warshall's algorithm, as apposed to the Floyd/Warshall algorithm. The result is basically a matrix that says "yes, there is a path from A to B" or "no, there is not."
Okay, so I figured out how to solve your actual problem. But now I'm wondering if this is a homework problem. If it is truly not, let me know and I'll post the answer.
"The result is basically a matrix that says "yes, there is a path from A to B" or "no, there is not.""
Well, FW algorithm actually finds the shortest paths too. To the OP: http://www.amazon.co.uk/IntroductionAlgorithmsThomasHCormen/dp/0262032937/ref=sr_1_2?ie=UTF8&s=books&qid=1213222038&sr=82
I am very sure we saw this exact same question in this forum within the past two years, probably one. Perhaps the OP is taking the same course as the previous poster.
The reason it sounds like a homework problem is that it doesn't have much practical application. Questions of more practical interest are finding a maximal set of disjoint paths, or a minimal set of disconnecting cut points.
Mikkin Wednesday, June 11, 2008
Hi,
This is the OP. This is not a homework problem, it's actually for work. We're developing a network simulator where we can define sources, sinks and intermediate nodes. The links between all of the nodes change every so often and I need to evaluate the network to see if there is a path from any source to any sink every time the links between the nodes change. So, I'm not concerned with shortest path, I just want to know if there is a link from a source to a sink. HOWEVER, the way our code works (it's not the way I would write it) is that all of the possible links from sources to sinks have to be defined in the beginning of the simulation. Every time the links change, we evaluate a set of node hops from source to sink to see if the network is up, hence my need for a complete set of paths from all sources to all sinks. By the way, thank you all for your responses!!
OP Wednesday, June 11, 2008
Okay, you probably want to do a breadthfirst search. Something like this:
Let Result = empty set Let Current = set of paths consisting of (source_i) (In other words, for each source S, create a path of length 0, starting at S) While (Current is not empty) { Let P = first element in Current. Pop P out of Current Let x = last vertex in P If (x is a sink) { Add P to Result continue with while loop } otherwise For each link (x, y) in the edge set { if (P contains y) { cycle  ignore and continue with for loop } Let P' = P + y Add P' to Current } }
That's a simple backtracking problem. Here is some pseudocode.
Given is a list of nodes and their connections. Each node is a source, a sink or a normal node, and each node has a WasVisited flag. It could either be a flag or a separate list/hashmap where visited nodes are stored. VisitNode (Source, Node) if Node.WasVisited then return Node.WasVisited = true if Node.IsSink then StoreResult(Source, Node) for each Target in Node.ConnectedNodes VisitNode(Source, Target) next (*) end VisitNode for each Source in SourceNodes ClearVisitedState(AllNodes) VisitNode(Source, Source) next This gives you a list of sourcesink connections. If you want to get ALL possible paths without loops, then add Node.WasVisited = false for the (*). Note that this may result in exponential behaviour, depending on the structure. And you should track the current path to store it, too. Of course the recursion behaviour can be optimized, or you could get rid of the recursion by using a queue like Michael, but premature optimization... you know...
Secure Thursday, June 12, 2008
By the way, it's really worth having a copy of Steven Skiena's _The Algorithm Design Manual_ on hand just to answer questions like this one.

Powered by FogBugz