One of the core functions in my multi-state mazes app automagically creates graphs that are conceptually like the one in the attached program. In this case, the shortest path from vertex 0 to vertex 11 is also the only simple path from vertex 0 to vertex 11. Also, unlike a regular maze, there are no dead ends (only cycles), so no matter how far one deviates from this simple path, there is always a way back. To that end, I'm trying to write a function that gives users a path to the end vertex (11) from any other vertex in the maze graph. Unfortunately, this function currently works properly only when given the start vertex (0). I've tried both breadth-first and depth-first search. The cycles seem to be throwing them off in a manner I haven't figured out, yet. I'll keep investigating the problem, but if anyone else has dealt with something like this before, please let me know how I should proceed. Cromwell D. Enage __________________________________ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail
On Dec 14, 2004, at 9:56 PM, Cromwell Enage wrote:
To that end, I'm trying to write a function that gives users a path to the end vertex (11) from any other vertex in the maze graph. Unfortunately, this function currently works properly only when given the start vertex (0).
I think you want to use breadth_first_search on a reverse_graph, starting from the end vertex. It'll handle cycles and will compute the shortest paths automagically. Of course, you'll need to change that "directedS" to "bidirectionalS" in your graph type. Doug
I think you want to use breadth_first_search on a reverse_graph, starting from the end vertex. It'll handle cycles and will compute the shortest paths automagically. Of course, you'll need to change
--- Douglas Gregor
"directedS" to "bidirectionalS" in your graph type.
I was going to use dijkstra_shortest_paths as a workaround, but your solution looks better. Thanks! Cromwell D. Enage __________________________________ Do you Yahoo!? Dress up your holiday email, Hollywood style. Learn more. http://celebrity.mail.yahoo.com
participants (2)
-
Cromwell Enage -
Douglas Gregor