<p>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</p>

<p>Finding the k shortest paths.
D. Eppstein.
<em>SIAM J. Computing</em> 28(2):652-673, 1998.
<a href="http://dx.doi.org/10.1137/S0097539795290477">doi:10.1137/S0097539795290477</a>.</p>

<p>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.</p>

<p>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.)</p>

<p>I had some implementations linked from <a href="http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html">my publication page</a> but the links are old and some of them may have gone dead by now.</p>

CC BY-SA 3.0
2013-08-12T03:12:48.057Z
2013-08-12T03:12:48.057Z
David Eppstein
<p>I have a directed graph that can have cycles and has weighted edges. </p>

<p>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).</p>

<p>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.</p>

<p>Then my result should be:</p>

<ul>
<li>C->C (Weight: 3)</li>
<li>C->C->C (Weight: 6)</li>
<li>C->C->C->C (Weight: 9)</li>
<li>C->C->C->C->C (Weight: 12)</li>
<li>C->C->C->C->C->C (Weight: 15)</li>
<li>C->C->C->C->C->C->C (Weight: 18)</li>
</ul>

<p>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.</p>

<p>I'm using an adjacency list as my underlying graph data structure <strong>(in C#)</strong></p>

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

<graph-theory><graph-algorithms>
Finding all paths with weight less than N from a source node
u1490
# Finding all paths with weight less than N from a source node

(Asked by: username_0 on 2013-08-11)

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.

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2013-08-12. Score: 6

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](http://dx.doi.org/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](http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html) but the links are old and some of them may have gone dead by now.


---

