floyd_warshall_numpy#
- floyd_warshall_numpy(G, nodelist=None, weight='weight')[源代码]#
使用Floyd算法查找所有对的最短路径长度。
这种寻找最短路径的算法利用了图的矩阵表示法,适用于需要所有对最短路径长度的稠密图。结果以NumPy数组的形式返回,距离 [i, j] ,其中i和j是节点列表中两个节点的索引。入门距离 [i, j] 是从i到j的最短路径上的距离。如果不存在路径,则距离为inf。
- 参数
- G网络X图表
- nodelist列表,可选(默认为G.Nodes)
行和列按节点列表中的节点排序。如果nodelist为NONE,则排序由G.node生成。节点列表应包括G中的所有节点。
- weight: string, optional (default='weight')
与边权重对应的边数据关键点。
- 返回
- distance2D数值.ndarray
节点之间的最短路径距离的数组。如果两个节点之间没有路径,则值为inf。
- 加薪
- NetworkXError
如果节点列表不是G中的节点列表。
笔记
当Dijkstra算法失效时,Floyd算法适用于在稠密图或负权图中寻找最短路径。如果存在负循环,该算法仍然可能失败。它有运行时间 \(O(n^3)\) 其运行空间为 \(O(n^2)\) 。