作者:水平蓝精灵天堂_678 | 来源:互联网 | 2022-12-07 11:50
假设我将边设置为包含边的列表,如下所示:
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之间的最小距离外,我还想将其推广到给定边集和距离矩阵的情况下,找到任意两个节点之间的最小距离。
1> TruBlu..:
尝试使用networkx
:
import networkx
shortest_path(G, source, target)
G是图。
源是起始节点。
目标是路径末端的节点。
shortest_path文档