<p>This comes down to counting the number of simple paths of length k between two given nodes, a question that is addressed e.g. here: <a href="https://cstheory.stackexchange.com/questions/20246/counting-the-number-of-simple-paths-in-undirected-graph">stackoverflow</a>. The problem is #P-complete, so not much hope for an efficient algorithm, I'm afraid.</p>

CC BY-SA 4.0
2019-05-21T10:39:26.600Z
2019-05-21T10:39:26.600Z
smapers
<p>I am trying to solve one graph traversing problem which might be classical to guys who are familiar with the topic. However, I am not. I have directed graph where nodes are cities and plane can fly from one to another. The network is quite complex. I have to find number of paths from e.g. Atlanta to Orlando with defined (zero, one, two…) number of stops. I do this by multiplying adjacency matrix exact number of times (repeated squaring) which gives distance matrix. The problem is how to eliminate redundant paths e.g. Atlanta-Boston-Atlanta-Orlando. This path has two stops which is O.K. from the algorithm point of view (if we need two stops) but makes no sense. Is there algorithm to eliminate such paths? </p>

<graph-theory>
Graph path problem
user120250
# Graph path problem

(Asked by: username_0 on 2019-05-21)

I am trying to solve one graph traversing problem which might be classical to guys who are familiar with the topic. However, I am not. I have directed graph where nodes are cities and plane can fly from one to another. The network is quite complex. I have to find number of paths from e.g. Atlanta to Orlando with defined (zero, one, two…) number of stops. I do this by multiplying adjacency matrix exact number of times (repeated squaring) which gives distance matrix. The problem is how to eliminate redundant paths e.g. Atlanta-Boston-Atlanta-Orlando. This path has two stops which is O.K. from the algorithm point of view (if we need two stops) but makes no sense. Is there algorithm to eliminate such paths?

**Tags:** graph-theory

---

## 1 answers

### Answer by username_1 on 2019-05-21. Score: 0 | Accepted answer

This comes down to counting the number of simple paths of length k between two given nodes, a question that is addressed e.g. here: [stackoverflow](https://cstheory.stackexchange.com/questions/20246/counting-the-number-of-simple-paths-in-undirected-graph). The problem is #P-complete, so not much hope for an efficient algorithm, I'm afraid.


---

