Thanks for the reply. Shortest-path, in my context, refers to a path, minimum in length but not necessarily Eulerian, that starts at a given vertex v_s and ends in a different vertex v_d, such that all edges are visited at least once. Therefore in graphs with loops this shortest path will necessarily be greater than the number of edges. I found a method of getting such a minimum path length. Essentially a virtual edge has to be added between v_s and v_d; then relabel these two vertices as odd/even taking into account the virtual edge as well. Finally solve the chinese-postman-problem on the original graph (without the virtual edge) but with the new relabellings of odd/even vertices. On Wed, 23 Mar 2011, Jeremiah Willcock wrote:

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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users