sklearn.utils.graph_shortest_path.graph_shortest_path

sklearn.utils.graph_shortest_path.graph_shortest_path()

Perform a shortest-path graph search on a positive directed or undirected graph.

Parameters:

dist_matrix : arraylike or sparse matrix, shape = (N,N)

Array of positive distances. If vertex i is connected to vertex j, then dist_matrix[i,j] gives the distance between the vertices. If vertex i is not connected to vertex j, then dist_matrix[i,j] = 0

directed : boolean

if True, then find the shortest path on a directed graph: only progress from a point to its neighbors, not the other way around. if False, then find the shortest path on an undirected graph: the algorithm can progress from a point to its neighbors and vice versa.

method : string [‘auto’|’FW’|’D’]

method to use. Options are ‘auto’ : attempt to choose the best method for the current problem ‘FW’ : Floyd-Warshall algorithm. O[N^3] ‘D’ : Dijkstra’s algorithm with Fibonacci stacks. O[(k+log(N))N^2]

Returns:

G : np.ndarray, float, shape = [N,N]

G[i,j] gives the shortest distance from point i to point j along the graph.

Notes

As currently implemented, Dijkstra’s algorithm does not work for graphs with direction-dependent distances when directed == False. i.e., if dist_matrix[i,j] and dist_matrix[j,i] are not equal and both are nonzero, method=’D’ will not necessarily yield the correct result.

Also, these routines have not been tested for graphs with negative distances. Negative distances can lead to infinite cycles that must be handled by specialized algorithms.