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_matrixarraylike 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

directedboolean

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.

methodstring [‘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

Gnp.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.