general idea and maybe example on graph

Question

I'm looking for a general idea (and maybe some code example or at least pseudocode) Now, this is from a problem that someone gave me, or rather showed me, I don't have to solve it, but I did most of the questions anyway, the problem that I'm having is this:

Let's say you have a directed weighted graph with the following nodes:

AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

and the question is: how many different routes from C to C with a distance of less than x. (say, 10, 20, 30, 40) The answer of different trips is: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

The main problem I'm having with it is that when I do DFS or BFS, my implementation first chooses the node and marks it as visited therefore I'm only able to find 2 paths which are CDC and CEBC and then my algorithm quits. If I don't mark it as visited then on the next iteration (or recursive call) it will choose the same node and not next available route, so I have to always mark them as visited however by doing that how can I get for example CEBCEBCEBC, which is pretty much bouncing between nodes.

I've looked at all the different algorithms books that I have at home and while every algorithm describes how to do DFS, BFS and find shortest paths (all the good stufF), none show how to iterate indefinitively and stop only when one reaches certain weight of the graph or hits certain vertex number of times.

Answer 1

So why not just keep branching and branching; at each node you will evaluate two things; has this particular path exceeded the weight limit (if so, terminate the branch) and is this node where I started (in which case log my path history to an 'acceptable solutions' list); then make new branches which each take a step in each possible direction.

Answer 2

In fact you have two different problems:

• Find all distinct cycles from C to C, we will call them C_1, C_2, ..., C_n (done with a DFS)
• Each C_i has a weight w_i, then you want every combination of cycles with a total weight less than N. This is a combinatorial problem (and seems to be easily solvable with dynamic programming).

Answer 3

You should not mark nodes as visited; as MikeB points out, CDCDC is a valid solution and yet it revisits D.

I'd do it lke this:

Start with two lists of paths:
 Solutions (empty) and
 ActivePaths (containing one path, "C").
While ActivePaths is not empty,
 Take a path out of ActivePaths (suppose it's "CD"[8]).
 If its distance is not over the limit,
  see where you are by looking at the last node in the path ("D").
  If you're at "C", add a copy of this path to Solutions.
  Now for each possible next destination ("C", "E")
   make a copy of this path, ("CD"[8])
   append the destination, ("CDC"[8])
   add the weight, ("CDC"[16])
   and put it in ActivePaths
 Discard the path.

Whether this turns out to be a DFS, a BFS or something else depends on where in ActivePaths you insert and remove paths.

No offense, but this is pretty simple and you're talking about consulting a lot of books for the answer. I'd suggest playing around with the simple examples until they become more obvious.