-2
$\begingroup$

I have a directed graph that can have cycles and has weighted edges.

I'm having a tough time finding all the different paths you can take from a source node S with a distance less than X (sum of edge weights).

Let's say my graph has a single node "C" which has an edge pointing to itself with a weight of 3. Let's also say that I want all paths with a distance less than 20.

Then my result should be:

  • C->C (Weight: 3)
  • C->C->C (Weight: 6)
  • C->C->C->C (Weight: 9)
  • C->C->C->C->C (Weight: 12)
  • C->C->C->C->C->C (Weight: 15)
  • C->C->C->C->C->C->C (Weight: 18)

Obviously, in the real scenario I have more than a single node. I'm just trying to illustrate the problem I'm trying to solve.

I'm using an adjacency list as my underlying graph data structure (in C#)

You don't have to show me the code, but it would be nice. Most importantly, please guide me in the right direction.

$\endgroup$
6
$\begingroup$

I'm not sure whether you want all paths from s to anywhere (in which case the problem is not research-level and shouldn't have been posted here) or from s to some specific destination t. In the s-t path case, try my paper

Finding the k shortest paths. D. Eppstein. SIAM J. Computing 28(2):652-673, 1998. doi:10.1137/S0097539795290477.

It's about a slightly different problem (its input is a count of how many paths you want rather than, as in your problem, a threshold on how long they should be) but your version is easier and can be solved in the same way. The paper describes a way of constructing an infinite tree of constant degree, each node of which represents a path, in which the parent of each node is a better path. All you have to do is a recursive traversal of this tree (e.g. depth first search) stopping and backtracking whenever it reaches a path of length greater than N.

The total time should be the time for a single pass of Dijkstra plus constant per path. (The paths are represented in an implicit way that allows them to be output in constant time each, or you could expand them and spend time proportional to their length.)

I had some implementations linked from my publication page but the links are old and some of them may have gone dead by now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.