Build a list using specific keys in a dict (python)?

Question

I'm implementing the Dijkstra search algorithm in Python. At the end of the search, I reconstruct the shortest path using a predecessor map, starting with the destination node's predecessor. For example:

path = []
path.append(destination)
previous = predecessor_map[destination]
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

Is there any way to do this with less lines of code (e.g. list comprehension)?

Answer 1

The only suggestion that I have is to get rid of the slight code duplication:

path = []
previous = destination
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

Beyond that, I think your code is actually very clear and is unlikely to benefit from any attempts to shorten it.

Lastly, it is worth noting that the above also works when destination == origin, whereas your original version most probably doesn't (depends on how exactly predecessor_map is populated). Don't know if this is relevant to your use cases.

Answer 2

This might work:

path = [destination]
path += iter(lambda: predecessor_map[path[-1]], origin)

It behaves the same as your original code. But what you've already written is fine as is.

If destination could be equal to origin:

path = []
path += iter(lambda: predecessor_map[path[-1]] if path else destination, origin)

It behaves the same as @aix's code.