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'不一定会得出正确的结果。

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