I'm looking for an algorithm which achieves the following: Given a directed, unweighted graph G and nodes g[i] and g[j] in G, find the shortest path from g[i] to g[j]. Use a single breadth-first traversal of G, marking visited nodes as you go. This is essentially a tree traversal problem. The trick is to end up with an ordered list of nodes representing the path (i.e. "traverse to g13, then to g42, then to ...") like you would after completing a depth-first search, even though you're actually doing a breadth-first search. Is this a well-known problem? I imagine it can be solved using an auxiliary list to keep track of "parents", but so far I haven't hit upon the right combination of stack and queue operations to do the job. Btw. this is something I'm curious about and want for my pet programming language (not a homework assigment).
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
