我正在嘗試使用Dijkstra和A Star算法（在定向NetworkX圖中）計算2點之間的最短路徑。如何在NetworkX圖表中限制某些路徑？
目前，它工作正常，我可以看到計算的路徑，但我想找到的方式限制一定路徑。
例如，如果我們有如下的節點：
節點= [1,2,3,4]
隨着這些邊緣：
邊緣=（（1,2），（2 ，3），（3,4））
是否有阻擋/限制的方式1 - > 2 - > 3但仍允許2 - > 3 & 1 - > 2。
這將意味着：
可以旅行從1到2
可以行程2至3
不能行程1至3個..直接或間接（即限制1-> 2-> 3路徑）。
這是否可以在NetworkX中實現..如果沒有，Python中是否會有另一個圖形庫允許這樣做？
謝謝。
有趣的問題，我從來沒有聽說過這個問題，可能是因爲我沒有太多的背景在這個主題中，也沒有太多的經驗與NetworkX。但是，我確實有一個算法的想法。這可能是最簡單的方法，我很樂意聽到一個更聰明的算法。
這個想法是，您可以使用您的限制規則將圖轉換爲所有邊有效的新圖，使用以下算法。
路徑（1,2,3）的限制，可以在兩種規則被分割（2,3）然後刪除（1,2）
把這個放在圖中，你可以爲每個案例插入節點2的副本。我將在相應情況下的有效邊緣之後調用新節點1_2和2_3。對於這兩個節點，您將所有傳入和傳出邊緣減去限制邊緣。
例如：
Nodes = [1,2,3,4]
Edges = [(1,2),(2,3),(4,2)]
的有效路徑，應僅是4-> 2-> 3不1-> 2-> 3。所以我們展開圖：
Nodes = [1,1_2,2_3,3,4] # insert the two states of 2
Edges = [ # first case: no (1_2,3) because of the restriction
(1,1_2), (4, 1_2)
# 2nd case, no (1,2_3)
(2_3,3), (4,2_3)]
此圖中唯一有效的路徑是4-> 2_3-> 3。這只是在原始圖中映射爲4-> 2-> 3。
我希望這個答案至少可以幫助你，如果你找不到現有的解決方案。更長的限制規則會使狀態節點的數量呈指數級增長，從而導致圖形爆炸，所以要麼這個算法太簡單，要麼很難;-)
看起來非常漂亮，但我不確定我完全理解你的方法。因此，1_2和any_2具有所有傳入/傳出邊緣，除了1_2不會有1_2-> 3，並且any_2不會有1-> any_2？我在問這個問題，因爲似乎在處理兩個邊1-> 2和2-> 3之間存在一些不對稱。 – yosukesabai
我想知道的另一件事是，問題不僅允許1-> 2-> 3不僅直接，而且還間接**。在你的設置中，禁止像1-> 2-> 5-> 6-> 7-> 3-> 4的路徑尋找從1到4的路徑？該路徑間接包括1-> 2-> 3。 – yosukesabai
@yosukesabai：好點，我想我確定了你的第一點。關於第二條評論，我解釋了這個問題只排除了一個沒有任何中間節點的受限路徑。我不確定它是如何與中間體解決的。 –
您可以設置您的節點數據{color = ['blue' ]}，節點2有{color = ['red'，'blue']}，node3有{color = ['red']}。然後使用networkx.algorithms。 astar_path（）方法設置
我不知道這是否可以在NetworkX內部完成，但是（概念上）簡單的方法是觀察節點1，如果它被使用，則完全刪除節點3。 – Wilduck