使用Boost的圖breadth_first_search（）在未加權的無向圖中查找路徑

我使用了一個adjacency_list圖，具有無向和不加權的邊。我需要找到頂點u和頂點v之間的最短路徑。我應該從u開始使用breadth_first_search（）嗎？到達v時，如何獲得路徑，以及如何停止搜索？使用Boost的圖breadth_first_search（）在未加權的無向圖中查找路徑

謝謝！

來源

2009-01-14 kbo

也許這將有助於上手：http://stackoverflow.com/questions/14126/how-to-create-ac -boost-undirected-graph-and-traverse-it-in-depth-first-search – Frank 2009-02-24 16:05:09

您應該使用最短路徑算法之一Dijkstra Shortest Path是最合適的，因爲您需要在兩個頂點之間找到路徑。有一個example在助推發行中的使用。有幾種方法可以獲得該功能的輸出：通過提供距離屬性圖或構建前驅圖或編寫自定義訪問者。

來源

2009-02-25 14:46:44 hvintus

-2

您需要使用minimum spanning tree：搜索算法。這是一個非常簡單直接的貪婪算法。

來源

2009-01-14 13:03:17

如果我沒有弄錯，最小生成樹不一定包含兩個特定頂點之間的最短路徑。 – kbo 2009-01-14 13:19:47

我認爲大多數最小生成樹算法都不是貪婪的（在做出貪婪，次優選擇的意義上），但他們實際上找到了最優的最小生成樹。 – Frank 2009-02-24 16:06:45

是的，從u開始執行breadth_first_search（）。

FOR every vertex i meet 
    IF i==v: BREAK 
    record predecessor of i as i.p

找到最短路徑，從V開始：

PRINT_PATH(u, v) 
    IF v==u 
    print u 
    ELSEIF v.p==NIL 
    print 'no path from u to v exists' 
    ELSE PRINT_PATH(u, v.p) 
    print v

來源

2010-06-24 10:20:07

使用Boost的圖breadth_first_search（）在未加權的無向圖中查找路徑

回答

相關問題