0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Emil Jeřábek, Community May 21 at 11:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

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. The problem is #P-complete, so not much hope for an efficient algorithm, I'm afraid.

$\endgroup$

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