基于Python图的DAG中的有效最短路径

Question

任务：我想使用Python的graph-tool高效地计算DAG（有向无环图）中源节点和目标节点之间的最短路径。我的狗有负重。在

理论上，这是一个计算上“容易”的问题（即，O（V+e）），首先计算图的拓扑排序，然后访问和更新父节点和距离（例如，如所讨论的here）。在

如何使用graph-tool有效地实现这一点？在

到目前为止我失败的尝试：

• 在Python中手动实现理论上有效的算法。但是，由于我必须在图中的每个顶点上循环，这会变得非常缓慢
• 使用来自graph-tool的shortest_path函数从Boost Graph Library调用Dijkstra例程将有一个可接受的运行时间，但不能完全利用DAG结构，而且无论如何也不适用于负权重
• 使用shortest_path调用Bellman-Ford返回正确的最短路径，但没有利用DAG结构，而且速度太慢（O（VE））。在

有效的DAG最短路径算法在底层Boost Graph Library中被实现为dag_shortest_paths。有没有什么方法可以通过graph-tool来访问这个函数，或者用graph-tool有效地计算这个函数？在

Answer 1

你试过使用Networkx库吗？因为我知道，它是有效的，适用于加权和非加权图，而且使用起来非常简单。在

https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path

例如：

    >>> import networkx as nx

    >>> G=nx.path_graph(5)
    >>> path=nx.all_pairs_dijkstra_path(G)
    >>> print(path[0][4])

[0, 1, 2, 3, 4]

Answer 2

此功能已添加到git版本的graph tool中：

https://git.skewed.de/count0/graph-tool/commit/012787ecde818efc2b893ad0d8aff819b8deb6ca

一个可选参数dag=True现在可以传递给shortest_path()，它可以达到您想要的效果。在