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.

Question

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

Answer 1

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