sklearn.utils.sklearn.utils.graph_shortest_path.graph_shortest_path

sklearn.utils.graph_shortest_path.graph_shortest_path()

对正有向图或无向图执行最短路径图搜索。

参数 说明
dist_matrix arraylike or sparse matrix, shape = (N,N)
正距离数组。 如果顶点i连接到顶点j，则dist_matrix [i,j]给出顶点之间的距离。 如果顶点i未连接到顶点j，则dist_matrix [i,j] = 0
directed boolean
如果为真，则在有向图上找到最短路径：仅从一个点到其相邻点，而不是反过来。 如果为假，则在无向图上找到最短路径：该算法可以从一个点前进到其相邻点，反之亦然。
method string [‘auto’，’FW’，’D’]
使用方法。 选项为“auto”：尝试为当前问题选择最佳方法。“FW”：Floyd-Warshall算法。 O [N ^ 3]“ D”：Dijkstra的斐波那契堆栈算法。 O [（k + log（N））N ^ 2]
返回值 说明
G np.ndarray, float, shape = [N,N]
G [i，j]给出沿曲线图从点i到点j的最短距离。

注:

按照目前的实现方式，当有向== False时，Dijkstra的算法不适用于方向与距离相关的图形。 也就是说，如果dist_matrix [i,j]和dist_matrix [j,i]不相等且都不为零，则method ='D'不一定会得出正确的结果。

同样，这些例程尚未针对负距离的图形进行过测试。 负距离会导致无限循环，必须由专门的算法处理。