使用C進行圖形導航＃

Question

我有一點困惑，試圖想出一個好的算法來導航下面的圖形。

alt text http://www.archimedesinc.biz/images/StackOverflow/Tree.jpg

如果用戶選擇「表21」爲出發點，我需要能夠從出發臺到任何其他表的路徑。

EX：如果用戶選擇「表21」作爲開始，然後從「表8」增加了一個值，我需要創建以下路徑「表21 - >表12 - >表9→表6→表8「，表之間的所有權重是相同的。

我似乎已經忘記了我在處理有向圖的能力，並且想不出一個好的算法。我不是在尋求解決方案，而只是朝着正確的方向前進。

謝謝！

Answer 1

廣度優先搜索會找到最短路徑：既然你說的邊緣都是相同重量的http://en.wikipedia.org/wiki/Breadth-first_search

Answer 2

，Dijkstra's algorithm（對於這種事情我平時的第一選擇）將只下降到breadth first search所以我建議使用它來簡化。

Answer 3

您可以從多種算法中選擇以確定最短路徑。 QuickGraph擅長這類事情。