# Is there any algorithm that can find all the path from s to t if we require the path to have a total weight of K.

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

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

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