I'm looking for an algorithm to find the longest path between two nodes in a bidirectional, unweighted, cyclic graph.The path must not have repeated vertices (otherwise the path would be infinite of course).Would someone point me a to a good one (site or explain)?The graph will be sparse.Thanks for any help!
Finding the longest path between two nodes in a bidirectional unweighted graph
ds.algorithms;graph algorithms
You can solve your problem in $O(n^2 2^n)$ on a graph with $n$ vertices by dynamic programming. Let $G=(V,E)$ be an undirected graph with edge weights $d_{uv}$. Let $L(v,S)$ be the length of the longest path from some fixed vertex $s$ to vertex $v$, which visits no vertex in $S$. $L$ satisfies$$L(v,S)=\begin{cases} \max_{w\in N(v)\setminus S} d_{vw}+L(w,S\cup\{w\}) & v\neq s\\ 0 & \text{otherwise} \end{cases}\mathrm{,}$$where $N(v)$ is the set of $v$'s neighbors. (Define the empty $\max$ to be $-\infty$.) Then the longest path between $s$ and $v$ has length $L(v,\{v\})$.