所有使用graph_tool的最短路徑

我想知道graph_tool中是否有內置函數可用於查找全部從節點s到節點t的最短路徑。所有使用graph_tool的最短路徑

如果沒有，有什麼辦法可以使用shortest_distance（）（在模塊graph_tool.topology中）或shortest_path（）（在模塊graph_tool.topology中）以某種方式（或任何其他內置函數）來計算所有最短的路徑，而不是其中的一個，我正在使用一個有大約50萬個節點的圖形。

來源

2014-07-14 Bahar

圖形工具中沒有這樣的功能。請注意，一般情況下，查找大圖上的所有最短路徑可能都是不可行的，因爲最短路徑的數量將與圖的大小組合在一起。

UPDATE：本all_shortest_paths()功能最近已添加到庫中，這恰恰不要求什麼：

https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.all_shortest_paths

來源

2014-09-27 08:18:13

但distance_histogram功能是超級快。與最短路徑有什麼不同？ – Moj

@Moj因爲它計算對之間的_shortest distance_，而不是所有對之間的所有最短路徑_，這是原始問題。 –

所有使用graph_tool的最短路徑

回答

相關問題