I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?
If the input graph is undirected:
If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.
If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.
Otherwise, there are infinitely many walks from $s$ to $t$.
If the input graph is directed:
Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable. Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$. Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.
If $H$ is empty, there are no walks from $s$ to $t$.
If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a simple path. The number of paths in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming. Remaining details are left as a homework exercise.
Otherwise, there are infinitely many walk from $s$ to $t$.