Compute the shortest path lengths using Johnson’s algorithm.
Johnson’s algorithm combines the Bellman-Ford algorithm and Dijkstra’s algorithm to quickly find shortest paths in a way that is robust to the presence of negative cycles. If a negative cycle is detected, an error is raised. For graphs without negative edge weights, dijkstra() may be faster.
csgraph : array, matrix, or sparse matrix, 2 dimensions
directed : bool, optional
indices : array_like or int, optional
return_predecessors : bool, optional
unweighted : bool, optional
dist_matrix : ndarray
predecessors : ndarray
This routine is specially designed for graphs with negative edge weights. If all edge weights are positive, then Dijkstra’s algorithm is a better choice.