python - 采用图形的 A* 算法

Question

我正在做一个项目，我需要一个最短路径算法来找到最短路径。目前我正在使用 David Eppstein 的 Dijkstra 算法的实现，但由于图的性质很大（大约 360 万个节点），找到这条最短路径可能需要将近一分钟。我知道 A* 算法运行得更快，但是我发现的所有 I 实现都基于网格样式而不是图形样式。示例图如下所示：

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 图形库，它实现 了所有常见的最短路径算法。