Finding all the shortest paths between two nodes i

问题:

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?

回答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 is a relatively straightforward 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.

Hope this helps!

回答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

回答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.

回答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.

回答5:

templatetypedef your answer was very good, thank you a lot for that one(!!), but it missed out one point:

If you have a graph like this:

A-B-C-E-F
  |     |
  D------

Now lets imagine I want this path:

A -> E.

It will expand like this:

 A-> B -> D-> C -> F -> E.

The problem there is, that you will have F as a parent of E, but

 A->B->D->F-E 

is longer than

 A->B->C->E.

You will have to take of tracking the distances of parents you are so happily adding.

回答6:

Step 1: Traverse the graph from the source by BFS and assign each node the minimal distance from the source

Step 2: The distance assigned to the target node is the shortest length

Step 3: From source, do a DFS search along all paths where the minimal distance is increased one by one until the target node is reached or the shortest length is reached. Print the path whenever the target node is reached.

回答7:

BFS stops when you find what you want.

You have to modify the algorithm so it continues its execution when the first path is found. (delete the return statement and save the path somehow.

You may end the execution after check the last node of the level that has the ending nodes of the shortest paths. (All ending nodes of the shortest paths are at the same level)

---

Also, there known algorithm that find all shortest paths:

Floyd–Warshall algorithm (it has pseudocode)

Johnson's algorithm