Subject: Re: [Boost-users] Traversing a graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-03-23 06:07:02
On Mon, 21 Mar 2011, Vipin Varma wrote:
> Hi,
>
> I have a quick question about graph traversal: what is the appropriate
> algorithm to be used if I want to find the shortest distance between 2
> specified vertices {v_s, v_d} such that every edge on the graph is traversed
> at least once? I've already used the breadth_first_search() and
> dijkstras_shortest_paths() for other problems wherein v_s = v_d. Seemingly,
> these algorithms cannot be used when the source and destination vertices are
> dissimilar.
What do you mean by "shortest path" in this context? Every path that
meets the criteria you describe will have exactly |E| edges, where E is
the edge set of the graph. I looked at the Wikipedia page on Eulerian
tours, and they show two separate algorithms; which one are you using?
Cycle-finding? In that case, I would recommend DFS since it is likely to
use less memory than BFS and they are equally good at finding cycles.
-- Jeremiah Willcock