How to find a path in graph with maximum edges?

Given a directed graph G=(V,E) and subset of vertices V', find the shortest path that visits all vertices in V' exactly once and never revisits any vertex in V.

• Without the last condition, a reasonable approach would be to use Floyd-Warshall (or Dijkstra's, etc.) to precompute all pairwise shortest-path-distances for V', call these E', and use a TSP heuristic to approximate the shortest Hamiltonian path through the graph G' = (V', E'). With the last condition, this approach fails, e.g. when two shortest paths have overlapping vertices, allowing revisits.

• Answer:

  This appears to be equivalent to finding a minimum weight Hamiltonian path in the graph [math]G^{'} = \left(V^{'}, E \cap \left(V^{'} \times V^{'}\right)\right)[/math].  So you can just any algorithm for that.