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算法。