python之在具有负权重的 DAG 上使用 python-IGraph 查找最短路径_编程设计

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

尝试过:我在文档中找到的最接近的匹配项是 <a href="http://pythonhosted.org/python-igraph/igraph.GraphBase-class.html#get_shortest_paths" rel="noreferrer noopener nofollow">get_shortest_paths</a> .但是，当尝试该函数时返回: 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选择了正确的内部算法？
或者可以明确指定算法 ( as in the R interface )

相关问题:

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

谢谢。

附言。 Python 2.7，IGraph 0.6.5

请您参考如下方法:

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

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