使用 Python 的图形工具在 DAG 中实现高效的最短路径

Question

任务： 我想使用 Python 的 [=11= 计算 DAG（有向无环图）中源节点和目标节点之间的最短路径] 高效。我的 DAG 有负权重。

理论上，这是一个计算 "easy" 问题（即 O(V + E)），首先计算图的拓扑排序，然后访问并更新父节点和距离（例如 here 所讨论的）。

我如何使用 graph-tool 有效地实现它？

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

手动实现 Python 中理论上有效的算法。然而，由于我必须遍历图中的每个顶点，这变得慢得令人无法接受
使用 graph-tool 中的 shortest_path 函数调用 Boost Graph Library 中的 Dijkstra 例程会有可接受的运行时间，但没有完全利用 DAG 结构和无论如何都不适用于负权重
使用shortest_path调用Bellman-Ford returns一条正确的最短路径，但没有利用DAG结构而且速度太慢(O(VE) ).

高效的DAG最短路径算法在底层Boost Graph Library中实现为dag_shortest_paths。是否有任何方法可以通过 graph-tool 访问此函数或使用 graph-tool 有效计算此函数的任何其他方法？

Answer 1

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

一个例子：

    >>> 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 版的图形工具中：

现在可以将可选参数 dag=True 传递给 shortest_path() 以实现您想要的效果。

Efficient shortest path in DAG with Python's graph-tool