A *算法採用圖形

Question

我正在開發一個項目，我需要最短路徑算法來找到最短路徑。目前我正在使用David Eppstein的Dijkstra算法的實現，但由於圖的大性（約360萬個節點），找到這條最短路徑可能需要幾分鐘的時間。我知道A *算法運行速度更快，但我發現的所有實現都基於網格樣式和圖形樣式。示例圖如下所示：

graph = {"A": {"B": 2} 
    "B": {"A": 2, "C": 5, "D": 4} 
    "C": {"B": 5, "E": 7} 
    "D": {"B": 4, "E": 10} 
    "E": {"C": 7, "D": 10} 
    } 

如果有人知道在線實現A *接受這種圖形作爲輸入的一些代碼，請讓我知道。

Answer 1

有一個叫做NetworkX 的python圖庫，它實現了所有常見的shortest path算法。