sklearn.utils.graph_shortest_path.graph_shortest_path

sklearn.utils.graph_shortest_path.graph_shortest_path()

Realiza una búsqueda del camino más corto en un grafo positivo dirigido o no dirigido.

Parámetros

dist_matrixarray-like o matriz dispersa, forma = (N,N)

Arreglo de distancias positivas. Si el vértice i está conectado al vértice j, entonces dist_matrix[i,j] da la distancia entre los vértices. Si el vértice i no está conectado al vértice j, entonces dist_matrix[i,j] = 0

directedboolean

si es True, entonces encuentra el camino más corto en un grafo dirigido: sólo progresa de un punto a sus vecinos, no al revés. si es False, entonces encuentra el camino más corto en un grafo no dirigido: el algoritmo puede progresar de un punto a sus vecinos y viceversa.

methodstring [“auto”|”FW”|”D”]

método a utilizar. Las opciones son “auto” : intenta elegir el mejor método para el problema actual “FW” : algoritmo de Floyd-Warshall. O[N^3] “D” : algoritmo de Dijkstra con pilas de Fibonacci. O[(k+log(N))N^2]

Devuelve

Gnp.ndarray, float, shape = [N,N]

G[i,j] da la distancia más corta del punto i al punto j a lo largo del grafo.

Notas

Tal y como está implementado actualmente, el algoritmo de Dijkstra no funciona para grafos con distancias dependientes de la dirección cuando directed == False. Es decir, si dist_matrix[i,j] y dist_matrix[j,i] no son iguales y ambas son distintas de cero, method=”D” no necesariamente dará el resultado correcto.

Además, estas rutinas no han sido probadas para grafos con distancias negativas. Las distancias negativas pueden llevar a ciclos infinitos que deben ser manejados por algoritmos especializados.