使用帶負向權重的DAG上的python-IGraph查找最短路徑

Question

任務：使用Python接口作爲邊界/頂點列表，查找具有負權重的DAG（有向無環圖）的最短路徑單源/單目標設置。

試過：我在文檔中找到的最接近的匹配是get_shortest_paths。但是，如果嘗試函數返回： igraph._igraph.InternalError: Error at structural_properties.c:5220: Weight vector must be non-negative, Invalid value 似乎內部函數試圖應用Dijkstra算法並失敗。同時，根據文檔，其他最短路徑函數（shortest_paths,shortest_paths_dijkstra）能夠使算法適應圖的屬性。

問題：

• 有沒有在這種情況下使用替代的功能？
• 或如何使get_shortest_paths選擇了一個正確的內部算法？
• 或者可以在算法中明確指定（as in the R interface）

相關問題：

• 是IGRAPH能夠檢測圖爲DAG和使用更快的最短路徑算法的拓撲排序圖形？
• 自定義的python代碼是否會比通用內部igraph算法（大概用C++編寫）慢？ （| E |是成千上萬，| V |是以千計）

謝謝。

PS。 Python 2.7，IGraph 0.6.5

Answer 1

get_shortest_paths無法處理帶有負權重的圖形，因爲底層C庫尚未具有相應的igraph_get_shortest_paths_bellman_ford函數。它的確有一個igraph_get_shortest_paths_dijkstra，所以Python接口只是檢查你是否有權重，如果是，將呼叫重定向到igraph_get_shortest_paths_dijkstra，否則它只是調用igraph_get_shortest_paths（這是C層中的未加權版本）。相反，shortest_paths使用負權重，因爲C庫具有一個名爲igraph_shortest_paths_bellman_ford的函數，所以它在至少一個邊權重爲負時調用Bellman-Ford實現。

不幸的是，唯一的出路似乎是實現在C層igraph_get_shortest_paths_bellman_ford，然後更新Python接口妥善處理負權重。

解答相關的問題：

• 的igraph不檢查圖形是否運行相關功能的最短路徑前DAG。是的，在DAG中可以找到最短的路徑，但這種用例非常罕見，至今沒有人爲執行特殊情況而煩惱。

• 寫在純Python自定義代碼可能會比C實現慢，但它取決於你的問題。如果您的意思是Bellman-Ford算法，純Python的實現可能會比較慢，但它可能仍然可用於您擁有的圖表。你可以嘗試執行NetworkX;據我所知，NetworkX是純Python，人們仍然將它用於具有數萬個節點和邊緣的圖形。

Answer 2

我也有一個緩慢的R版本。對於200k的邊緣和30k的頂點需要大約20分鐘的時間，所以我分解並在R（但不包括Python;對不起）和igraph_get_shortest_paths_bellman_ford()中實現get.shortest.paths()，以得到具有負邊權重的圖。你可以試試我的嘟嘟嘟嘟here。

從我的R實施切換到C時，我經歷了100倍和1000倍的加速。