Find the paths between two given nodes?

Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn’t keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn’t only store one predecessor but a list of possible predecessors.

Then all possible paths are encoded in this function, and by traversing π recursively you get all possible path combinations.

One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al. and has subsequently been used in many University scripts on the subject. A Google search for “BFS pseudocode predecessor π” uproots this hit on Stack Exchange.

Leave a Comment