I am implementing the Floyd-Warshall algorithm to find shortest paths in a graph in Python . I've had a problem writing a recursive function to print such a shortest path using the 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)
I wanted to do it with generators, but I have come across something curious. This way doesn't work, because it only prints the last number :
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)
And this other way (just change build_path
) returns me a list with a number and a generator, totally useless:
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
How can I get something equivalent to the first version using generators?
In recursion everything is from back to front:
Ricardo has given the key with his answer, which is to use
yield from
, added in Python 3.3 :So the final solution is as simple as this:
In earlier versions of Python, this syntax can be followed, as @Darkhogg comments: