The shortest (in terms of weight) path, constrained to have exactly n (or at most n) edges, can be found in polynomial time. For instance, given your graph $G=(V,E)$ make an expanded graph $H$ that has as its vertices the pairs $(v,i)$ where $vin G$ and $0le ile n-1$. Draw an edge in $H$ from $(v,i)$ to $(w,i+1)$ whenever $G$ has an edge from $v$ to $w$, with the same weight. Then the shortest $n$-edge path in $G$ from $v$ to $w$ is the same as the shortest path in $H$ from $(v,0)$ to $(w,n)$. To look for paths in $G$ that are at most $n$ edges long, add to $H$ edges of weight zero from $(v,i)$ to $(v,i+1)$.
However, these paths allow repeated vertices and edges. If repetitions are disallowed, and $G$ has $n+1$ vertices, then the shortest length-$n$ path is just a Traveling salesman path, so of course it's NP-complete.
No comments:
Post a Comment