给定图的边（有向）列表，如何找到2个节点之间的距离？

Question

假设我将边设置为包含边的列表，如下所示：

E=[(1, 6), (1, 7), (2, 3), (2, 6), (3, 2), (3, 8), (4, 5), (4, 7), (5, 4), (5, 9), (6, 1), (6, 7), (6, 2), (7, 1), (7, 6), (7, 4), (8, 9), (8, 3), (9, 8), (9, 5)]

给定距离矩阵，我想找到节点8和4之间的最短路径（并且还要考虑存在两个等距离的最短路径的情况）：

C=[2.5, 5.59, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 1.0, 2.0, 2.5, 5.0, 2.0, 5.59, 5.0, 2.0, 5.0, 2.0, 5.0, 2.0]

其中的每个元素C（例如在第i个位置）对应于相应的边缘的第2个节点E（在第i个位置）之间的距离。

我偶然发现了一些类似的文章，鼓励使用Dijkstra的算法，但是我还没有找到在Python 3.5x中能做到这一点的文章（也许有，但是我找不到它..：/）

因此，除了上面提到的问题外，除了找到节点8和4之间的最小距离外，我还想将其推广到给定边集和距离矩阵的情况下，找到任意两个节点之间的最小距离。

Answer 1

尝试使用networkx：

import networkx
shortest_path(G, source, target)

• G是图。
• 源是起始节点。
• 目标是路径末端的节点。

shortest_path文档