針對兩個節點之間所有路徑的非常快的算法

我對python編碼非常陌生，我正在尋找一種算法，可以快速找到一個非常大的圖的起始節點和結束節點之間的所有路徑 - 比如圖它有大約1000個節點和10,000條邊。從起始節點到結束節點實際存在的路徑數量很少 - 十個或更少。爲了幫助更多地考慮問題的背景，考慮一個社交網絡 - 如果我有1000個朋友，並且我想知道我高中的最好朋友連接我大學的室友時有多少種方式，我不關心我的事實來自高中的最好的朋友與我所有的200名高中朋友相連，因爲這些路徑永遠不會導致我的室友。我想用這個python代碼做的事情是迅速將我的兩個朋友之間存在的路徑分開，並基本消除存在於這兩個節點周圍的所有「噪音」。針對兩個節點之間所有路徑的非常快的算法

我試圖實現一些代碼示例，所有這些示例在小型簡單圖形上都可以很好地工作。但是，當我嘗試將它們合併到我的大圖分析中時，它們都需要很長時間纔能有用。

您是否都有任何關於調查方法的建議（即networkx中已經創建的東西，甚至是關於使用堆棧還是遞歸的信息等等），要實現的代碼示例，甚至是其他路由蟒蛇追求？請記住，我是一個Python新手。

來源

2013-02-06 Garen Pledge

翻譯在這個崗位到Python的解決方案之一：http://stackoverflow.com/questions/58306/ graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices –

此外，這是：http://stackoverflow.com/questions/8922060/breadth-first-search-trace-path –

挑戰是知道當你找到他們全部。沒有檢查大量的節點，我認爲這是不可能的。該算法不能忽略你的200個朋友，因爲它不知道（沒有檢查他們和他們的更多朋友）他們沒有連接到你的室友。事實上，是不是要確定是否有通過這些朋友路徑搜索的整個點？ – Blckknght

就我個人而言，我會建議使用圖形數據庫。 Neo4j或雷克斯特春天的腦海。

當從Python中訪問這些有幾個庫可供選擇：

雖然它不會是不可能寫出這些的快/可擴展的Python版本，就我所知，目前沒有一個。

來源

2013-02-06 23:43:03 Wolph

也許你想要兩個節點之間的所有簡單（無重複節點）路徑？ NetworkX具有基於深度優先搜索的功能。見http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

的例子從那裏顯示的簡單路徑的數量可能很大：

>>> import networkx as nx 
>>> G = nx.complete_graph(4) 
>>> for path in nx.all_simple_paths(G, source=0, target=3): 
...  print(path) 
... 
[0, 1, 2, 3] 
[0, 1, 3] 
[0, 2, 1, 3] 
[0, 2, 3] 
[0, 3]

來源

2013-02-08 19:12:28 Aric

Aric，我注意到目前的實現在真實網絡上不能很好地擴展。有沒有潛在的解決方法？ –

針對兩個節點之間所有路徑的非常快的算法

回答

相關問題