Finding all the shortest paths between two nodes in unweighted undirected graph

Question

I need help finding all the shortest paths between two nodes in an unweighted undirected graph.

I am able to find one of the shortest paths using BFS, but so far I am lost as to how I could find and print out all of them.

Any idea of the algorithm / pseudocode I could use?

Solution 1

As a caveat, remember that there can be exponentially many shortest paths between two nodes in a graph. Any algorithm for this will potentially take exponential time.

That said, there are a few relatively straightforward algorithms that can find all the paths. Here's two.

BFS + Reverse DFS

When running a breadth-first search over a graph, you can tag each node with its distance from the start node. The start node is at distance 0, and then, whenever a new node is discovered for the first time, its distance is one plus the distance of the node that discovered it. So begin by running a BFS over the graph, writing down the distances to each node.

Once you have this, you can find a shortest path from the source to the destination as follows. Start at the destination, which will be at some distance d from the start node. Now, look at all nodes with edges entering the destination node. A shortest path from the source to the destination must end by following an edge from a node at distance d-1 to the destination at distance d. So, starting at the destination node, walk backwards across some edge to any node you'd like at distance d-1. From there, walk to a node at distance d-2, a node at distance d-3, etc. until you're back at the start node at distance 0.

This procedure will give you one path back in reverse order, and you can flip it at the end to get the overall path.

You can then find all the paths from the source to the destination by running a depth-first search from the end node back to the start node, at each point trying all possible ways to walk backwards from the current node to a previous node whose distance is exactly one less than the current node's distance.

(I personally think this is the easiest and cleanest way to find all possible paths, but that's just my opinion.)

BFS With Multiple Parents

This next algorithm is a modification to BFS that you can use as a preprocessing step to speed up generation of all possible paths. Remember that as BFS runs, it proceeds outwards in "layers," getting a single shortest path to all nodes at distance 0, then distance 1, then distance 2, etc. The motivating idea behind BFS is that any node at distance k + 1 from the start node must be connected by an edge to some node at distance k from the start node. BFS discovers this node at distance k + 1 by finding some path of length k to a node at distance k, then extending it by some edge.

If your goal is to find all shortest paths, then you can modify BFS by extending every path to a node at distance k to all the nodes at distance k + 1 that they connect to, rather than picking a single edge. To do this, modify BFS in the following way: whenever you process an edge by adding its endpoint in the processing queue, don't immediately mark that node as being done. Instead, insert that node into the queue annotated with which edge you followed to get to it. This will potentially let you insert the same node into the queue multiple times if there are multiple nodes that link to it. When you remove a node from the queue, then you mark it as being done and never insert it into the queue again. Similarly, rather than storing a single parent pointer, you'll store multiple parent pointers, one for each node that linked into that node.

If you do this modified BFS, you will end up with a DAG where every node will either be the start node and have no outgoing edges, or will be at distance k + 1 from the start node and will have a pointer to each node of distance k that it is connected to. From there, you can reconstruct all shortest paths from some node to the start node by listing of all possible paths from your node of choice back to the start node within the DAG. This can be done recursively:

• There is only one path from the start node to itself, namely the empty path.
• For any other node, the paths can be found by following each outgoing edge, then recursively extending those paths to yield a path back to the start node.

This approach takes more time and space than the one listed above because many of the paths found this way will not be moving in the direction of the destination node. However, it only requires a modification to BFS, rather than a BFS followed by a reverse search.

Hope this helps!

Solution 2

@templatetypedef is correct, but he forgot to mention about distance check that must be done before any parent links are added to node. This means that se keep the distance from source in each of nodes and increment by one the distance for children. We must skip this increment and parent addition in case the child was already visited and has the lower distance.

public void addParent(Node n) {
    // forbidding the parent it its level is equal to ours
    if (n.level == level) {
        return;
    }
    parents.add(n);

    level = n.level + 1;
}

The full java implementation can be found by the following link.

http://ideone.com/UluCBb

Solution 3

I encountered the similar problem while solving this https://oj.leetcode.com/problems/word-ladder-ii/

The way I tried to deal with is first find the shortest distance using BFS, lets say the shortest distance is d. Now apply DFS and in DFS recursive call don't go beyond recursive level d.

However this might end up exploring all paths as mentioned by @templatetypedef.

Solution 4

First, find the distance-to-start of all nodes using breadth-first search.

^{(if there are a lot of nodes, you can use A* and stop when top of the queue has distance-to-start > distance-to-start(end-node). This will give you all nodes that belong to some shortest path)}

Then just backtrack from the end-node. Anytime a node is connected to two (or more) nodes with a lower distance-to-start, you branch off into two (or more) paths.

View more solutions

Comments

[caesar]

@templatetypedef could you explain what do you mean when you say "To do this, modify BFS in the following way: whenever you process an edge by adding its endpoint in the processing queue, don't immediately mark that node as being done. Instead, insert that node into the queue annotated with which edge you followed to get to it" ?? I couldnt understant it fully.

[caesar]

@templatetypedef, now I got it,but I have a different question. When I come to final step,is there any other way to print shortest paths rather than recursion ?

[bitec]

Thank you for detailed description. I tried to implement according to your description ideone.com/2IUfcd (it's a bit messy as strings are used as keys in graph, that's what was necessary for another problem) Unfortunately it doesn't produce the correct result as prints not only the shortest paths. Of course, I can sort the result paths and leave only the shortest, but is this really what was necessary? Seems this is necessary to save nodes level and remove those parents that don't have k - 1 level during BFS traversing..

[bitec]

You are correct. I faced the same problem, we cannot simply modify parent links greedely, but we need to edit them as soon as we find the shorter paths during traversals

[Kaidul]

My logic was also same but I ended up getting Time limit exceeded

[cs95]

This would be an NP-Complete problem? Because you can verify the solution in polynomial time using Dijkstra's algorithm? Please correct me if I'm mistaken, thanks!

[templatetypedef]

Formally speaking, a problem can only be NP-complete if it’s a decision problem (one with a yes or no answer). This is a counting problem (one that asks for how many objects there are of some type), so it can’t be NP-complete. There’s a related class of problems called the #P problems, which are ones where the goal is to count how many solutions there are to a problem where answers can be checked quickly, and there’s a notion of #P-completeness for hard problems involving counting. I don’t know whether this one is #P-complete and I strongly suspect it isn’t since it has such nice substructure.

[Your IDE]

@bitec But according to ideone.com/2IUfcd (the link you've given), [1, 3, 8, 6, 7] is not a shortest path since it has one edge-length more in the path length compared to the other shortest paths.