2

任务：使用 igraph 库的 python 接口为具有负权重的 DAG（有向无环图）查找最短路径，作为单源/单目标设置中的边/顶点列表。

尝试过：我在文档中找到的最接近的匹配项是get_shortest_paths. 但是，当尝试函数返回时： igraph._igraph.InternalError: Error at structural_properties.c:5220: Weight vector must be non-negative, Invalid value 似乎函数在内部尝试应用 Dijkstra 算法并失败。同时，根据文档，其他最短路径函数 ( shortest_paths, shortest_paths_dijkstra) 能够使算法适应图的属性。

问题：

  • 在这种情况下是否可以使用替代功能？
  • 或者如何get_shortest_paths选择正确的内部算法？
  • 或者可以明确指定算法（如在 R 界面中）

相关问题：

  • igraph 是否能够检测到图是 DAG 并在拓扑排序图上使用更快的最短路径算法？
  • 用于此的自定义 python 代码是否一定比通用内部 igraph 的算法之一慢（可能是用 C++ 编写的）？（|E| 以万计，|V| 以千计）

谢谢。

PS。Python 2.7，IGraph 0.6.5

4

2 回答 2

3

get_shortest_paths无法处理具有负权重的图，因为底层 C 库还没有相应的igraph_get_shortest_paths_bellman_ford函数。它确实有一个igraph_get_shortest_paths_dijkstra，因此 Python 接口只是检查您是否有权重，如果有，则将调用重定向到igraph_get_shortest_paths_dijkstra，否则它只是调用igraph_get_shortest_paths（这是 C 层中的未加权版本）。相反，shortest_paths使用负权重是因为 C 库有一个名为的函数igraph_shortest_paths_bellman_ford，因此当至少有一个边权重为负时，它会调用 Bellman-Ford 实现。

不幸的是，唯一的出路似乎是igraph_get_shortest_paths_bellman_ford在 C 层中实现，然后更新 Python 接口以适当地处理负权重。

相关问题的回答：

  • igraph 在运行任何最短路径相关函数之前不会检查图是否为 DAG。是的，在 DAG 中可以更快地找到最短路径，但这种用例非常罕见，以至于到目前为止没有人费心去实现这种特殊情况。

  • 用纯 Python 编写的自定义代码可能比 C 实现慢，但这取决于您的问题。如果您特别指的是 Bellman-Ford 算法，那么纯 Python 实现很可能会更慢，但它可能仍可用于您拥有的图形。您可以尝试在NetworkX中实现；据我所知，NetworkX 是纯 Python，人们仍然将它用于具有数万个节点和边的图。

于 2013-07-26T23:22:31.630 回答
0

我也有一个慢速的 R 版本。200k 边和 30k 顶点大约需要 20 分钟，所以我分解并get.shortest.paths()在 R（但不是 Python；抱歉）和igraph_get_shortest_paths_bellman_ford()具有负边权重的图中实现。你可以在这里试试我的 R igraph 叉子。

从我的 R 实现切换到 C 时，我经历了 100 倍到 1000 倍的加速。

于 2015-03-22T23:41:22.580 回答