Estoy implementando en Python el algoritmo de Floyd-Warshall para hallar caminos mínimos en un grafo. He tenido un problema escribiendo una función recursiva para imprimir dicho camino mínimo utilizando la matriz de predecesores (del inglés predecessor matrix):
def print_path(p_ij, ii, jj):
"""Recursive function to reconstruct the shortest path from i to j.
"""
if ii != jj:
print_path(p_ij, ii, p_ij[ii, jj])
print(jj)
Quería hacerlo con generadores, pero me he topado con algo curioso. Esta forma no funciona, porque solo imprime el último número:
def build_path(p_ij, ii, jj):
"""Recursive function to reconstruct the shortest path from i to j.
"""
if ii != jj:
build_path(p_ij, ii, p_ij[ii, jj])
yield jj
def print_path(p_ij, ii, jj):
for jj in build_path(p_ij, ii, jj):
print(jj)
Y esta otra forma (solo cambio build_path
) me devuelve una lista con un número y un generador, totalmente inútil:
def build_path(p_ij, ii, jj):
"""Recursive function to reconstruct the shortest path from i to j.
"""
if ii != jj:
yield build_path(p_ij, ii, p_ij[ii, jj]) # <-- Añado un yield
yield jj
¿Cómo puedo conseguir algo equivalente a la primera versión usando generadores?
yield build_path(p_ij, ii, p_ij[ii, jj])
estas devolviendo un generador de generadores, no un generador de objetos del tipo dejj
. Con yield from 'delega' el generador y no crea generadores de generadores... En resumen, aunque Python es dinámico, los tipos importan.