Graph navigation with C#
-
03-07-2019 - |
Question
I having a bit of a quandry trying to come up with a good algorithm to navigate the following graph.
alt text http://www.archimedesinc.biz/images/StackOverflow/Tree.jpg
If a user chooses "Table 21" as a starting point, I need to be able to get the path to any other table from that starting table.
EX: If the user chooses "Table 21" as a start and then adds a value from "Table 8", I need to create the following path "Table 21 -> Table 12 -> Table 9 -> Table 6 -> Table 8", all of the weights between the tables are the same.
I seem to have forgotten my skills in dealing with directed graphs, and can't think of a good algorithm. I'm not asking for a solution, but just a push in the right direction.
Thank you!
Solution
Breadth-first search will find a shortest path: http://en.wikipedia.org/wiki/Breadth-first_search
OTHER TIPS
Since you said the edges are all of the same weight, Dijkstra's algorithm (my usual first choice for this sort of thing) will just degrade to breadth first search so I suggest using that for simplicity.
You can choose from a number of algorithms for determining the shortest path. QuickGraph is good at this sort of thing.