I'd like to find a set of paths from a start node to and an end node so that those paths collectively contain as many edges of the graph as possible.
Or more precisely: Given a directed graph which may contain cycles, and two vertices u and v, I would like to find a finite set P of paths from u to v, such that for any path q between u and v that is not in P, and any edge e in q, there is a path p in P that contains e. The vertices u and v may be the same.
In fact, an almost identical question has been asked: Directed Graph Traversal - All paths, but the very plausible answer has never been accepted or received an upvote, so I was wondering. That answer involves using a variant of Dijkstra or A* to iterate over all paths between u and v ordered by length.
From Is there a well-studied optimization to find the shortest path traversing every weighted edge through a graph? it seems that my question is also almost identical to the "Chinese Postman Problem", except I don't need to visit all the edges, just as many as I can, and I'm not interested in shortest paths, just any paths, and my edges are not weighed.
I was thinking of doing something like the first answer. Or perhaps condense the graph using Kosaraju, use straight Dijkstra to find all paths between u and v, and expand the "condensed" vertices by finding all cycles in the strongly connected components. But I haven't really got anywhere.
What would be the best plan to follow?
