How to find all shortest paths
Solution 1
A simpler way is to find all paths from source to destination using dfs. Now find the shortest paths among these paths. Here is a sudo code:
dfs(p,len)
if(visited[p])
return
if(p== destination)
paths.append(len)
return
visited[p]=1
for each w adjacent to p
dfs(w,len+1)
visited[p]=0
You can find the path by maintaining an array for paths. I will leave that to you as an assignment
Solution 2
You can easily do it by maintaining a list or vector of parents for each node. If two or more nodes ( say X, Y, Z) at the same distance from the starting node , leads to another node M , make all X , Y and Z as the parents of M.
You just have to add a check to see while adding a parent to the node whether that parent is in the same level as the previous parents.
By level , I mean the distance from the starting point.
This way you can get all the shortest paths by tracing back the parent vectors. Below is my C++ implementation.
I hope you know how to print the paths by starting from the destination ,tracing the parents and reach the starting point.
EDIT : Pseudo Code
bfs (start , end)
enqueue(start)
visited[start] = 1
while queue is NOT empty
currentNode = queue.front()
dequeue()
if(currentNode == end)
break
for each node adjacent to currentNode
if node is unvisited
visited[node] = visited[curr] + 1
enqueue(node)
parent[node].add(currentNode)
else if(currentNode is in same level as node's parents)
parent[node].add(currentNode)
return
Solution 3
If the graph is large, finding all paths from start to end and then selecting the shortest ones can be very inefficient. Here is a better algorithm:
Using BFS, label each node with its distance from the start node. Stop when you get to the end node.
def bfs_label(start, end): depth = {start: 0} nodes = [start] while nodes: next_nodes = [] for node in nodes: if node == end: return depth for neighbor in neighbors(node): if neighbor not in depth: depth[neighbor] = depth[node] + 1 fringe.append(neighbor)
Using DFS, find all paths from the start node to the end node such that the depth strictly increases for each step of the path.
def shortest_paths(node, end, depth, path=None): if path is None: path = [] path.append(node) if node == end: yield tuple(path) else: for neighbor in neighbors(node): if neighbor in depth and depth[neighbor] == depth[node]+1: for sp in shortest_paths(neighbor, end, depth, path): yield sp path.pop()
caesar
Updated on June 04, 2022Comments
-
caesar over 1 year
I have a graph and I want to find all shortest paths between two nodes. I've found a shortest path between two nodes by BFS. However, it just gives me one of the shortest paths if there exists one more than.
How could I get all of them using BFS?
I've implement my code from well-known BFS pseudocode.
Also, I have a adjacency list vector which holds adjacency vertices for all nodes. -
Pham Trung almost 10 yearsSorry, but this is wrong, you can not use dfs to find all paths from source to target. For example you will miss one of the two cases: 1->2->3->4 and 1->3->4. If you want to find "all" path, a recursive will be required, not dfs.
-
Pham Trung almost 10 yearsBy the way,this quesion is duplicated stackoverflow.com/questions/14144071/…
-
caesar almost 10 yearsthanks to you, I got parents information correctly,however,I have no idea how could I print path by backtracing without recursion, do you have any hint ?
-
soup_boy almost 10 yearsyes, you can use a stack and do it iteratively. I will post the pseudocode shortly.
-
Bernhard Barker almost 10 yearsNote that this is a very inefficient way of doing things. Consider a graph with a billion nodes and the shortest path between the two target nodes is of length 5. You'll be exploring all the nodes rather than just those distance 5 from the source node. Modified BFS is a lot better.
-
Bernhard Barker almost 10 years@PhamTrung DFS is recursive. For the
1
node, it will first go to2
, and find1->2->3->4
and then it will backtrack back to1
and go to3
and find1->3->4
. And you duplicate comment would probably have been better suited as a comment on the question or a duplicate flag (I just flagged it). -
Pham Trung almost 10 years@Dukeling, What i mean is complete search by recursive :) sorry, this code is not dfs, i misunderstood it :D and storing path in array is not a good idea as the path can already contain the current node, which need a further check
-
soup_boy almost 10 yearsThe answer posted by banarun will work for printing all the paths. Use the parent vectors instead of the adjacency list. Start from the destination and trace all the paths to the starting node.