相关疑难解决方法(0)

我使用python绑定到igraph来表示有向树.我想找到从该图中的一个节点到另一个节点的所有可能路径.不幸的是,我无法在执行此任务的igraph中找到准备使用的功能？

编辑

对无限数量路径的关注

我所说的图实际上是一个带有单根的有向无环图(DAG).它代表了一个单向的级联事件,在级联的各个级别上,可以分裂或连接在一起.正如我所说,这是一个单向图.还规定图表不包含任何循环.由于这两个原因,无限的路径列表是不可能的.

我想做什么？

我的目标是找到从图形顶部(根)到给定节点的所有可能路径.

我正在尝试制作一个小型公共交通路线应用程序.

我的数据以下列结构表示:

graph = {'A': {'B':3, 'C':5},
     'B': {'C':2, 'D':2},
     'C': {'D':1},
     'D': {'C':3},
     'E': {'F':8},
     'F': {'C':2}}

哪里:

1. 图形dict键是一个节点
2. subdict键是2个节点之间的边
3. subdict value是边缘权重

我正在使用这里描述的find_shortest_path算法https://www.python.org/doc/essays/graphs/但由于递归而且它没有权重支持,所以它相当慢.

所以我转到Davide Epstein描述的算法http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/(甚至更好的实现可以在评论中找到使用heapq)

它工作得很好,它真的很快,但我只获得最佳路线而不是所有可能路线的列表.这就是我陷入困境的地方.

有人可以帮助我,或者至少给出指示？我在图最短路径算法方面不是很好.

提前致谢!