For a given positive integer K, is there any algorithm that can find all the path from s to t, which has exactly length of K. Given that the graph is directed and weighted and all the weight are positive.
The runtime should be at most O(K(|V|+|E|))
(All the vertex can be visited more than once.)

  • $\begingroup$ Dynamic programming? $\endgroup$ – Irvan May 3 '18 at 5:55
  • $\begingroup$ "Is there an algorithm?" Of course, enumerate all the $s\to t$ paths and see if any have length $K$. $\endgroup$ – Math1000 May 3 '18 at 6:07
  • $\begingroup$ sorry, forgot to say that this algorithm should be in O(K(|V|+|E|)) $\endgroup$ – Andy May 3 '18 at 6:29

I do not think so. The thing is that there could be "too many" paths for algorithm to report fast enough.

For example, consider a graph of 5 nodes. There is a central node $c$, it is connected to all four other nodes $s$, $t$, $A$ and $B$ in both directions, the length of these edges is 1. Any path from $s$ to $t$ looks like $s -> c ->... -> A -> c ... -> B -> c ... -> t$. (We move to $c$, than several steps either to $A$ or to $B$ and back, and final move to $t$). Path of weight $K$ exists only for even $K$, and there are at least $2^{K/2-1}$ such paths (and this number includes only paths which do not visit $s$ and $t$ in the middle).


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.