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