Python scipy.sparse.csgraph.shortest_path 示例说明

表示输入图的 N x N 距离数组。

用于最短路径的算法。选项是：

‘auto’ - (default) select the best among ‘FW’, ‘D’, ‘BF’, or ‘J’

based on the input data.

‘FW’ - Floyd-Warshall algorithm. Computational cost is

approximately O[N^3]. The input csgraph will be converted to a dense representation.

‘D’ - Dijkstra’s algorithm with Fibonacci heaps. Computational

cost is approximately O[N(N*k + N*log(N))], where k is the average number of connected edges per node. The input csgraph will be converted to a csr representation.

‘BF’ - Bellman-Ford algorithm. This algorithm can be used when

weights are negative. If a negative cycle is encountered, an error will be raised. Computational cost is approximately O[N(N^2 k)], where k is the average number of connected edges per node. The input csgraph will be converted to a csr representation.

‘J’ - Johnson’s algorithm. Like the Bellman-Ford algorithm,

Johnson’s algorithm is designed for use when the weights are negative. It combines the Bellman-Ford algorithm with Dijkstra’s algorithm for faster computation.

如果为 True(默认)，则在有向图上找到最短路径：仅沿路径 csgraph[i, j] 从点 i 移动到点 j。如果为 False，则在无向图上求最短路径：算法可以从点 i 沿 csgraph[i, j] 或 csgraph[j, i] 前进到 j

如果为 True，则返回大小 (N, N) 前导矩阵

如果为真，则找到未加权的距离。也就是说，不是找到每个点之间的路径以使权重之和最小化，而是找到使边数最小化的路径。

如果为 True，则用结果覆盖 csgraph。这仅适用于 method == ‘FW’ 且 csgraph 是密集的 c-ordered 数组且 dtype=float64 的情况。

如果指定，则仅计算给定索引处的点的路径。与方法 == 'FW' 不兼容。