# How to find all paths between two graph nodes

How to find all paths between two graph nodes like in the image below? I tried the Breadth-first search (BFS) algorithm, but although it can find all the points it can not find all the paths starting from (S)tart to (E)nd. I also tried the Depth-first search (DFS), which comes a lot closer. However when applying that tactic, because there is a closed list it will only find one path, probably the red line and since purple and green are crossing the closed list at that area those paths will be ignored.

I like to know how I can get all the paths from (S)tart to (E)nd. In the case below:

- D1, C1, B1, B2, A2, A1 (RED LINE PATH)
- D1, C1, C2, B2, A2, A1 (PURPLE LINE PATH)
- D1, D2, C2, B2, A2, A1 (GREEN LINE PATH)
- D1, D2, C2, C1, B1, B2, A2, A1 (YELLOW LINE PATH)

## Answers

Dijkstra's Algorithm (here, in Python) works great:

def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] if start not in graph: return [] paths = [] for node in graph[start]: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths def min_path(graph, start, end): paths=find_all_paths(graph,start,end) mt=10**99 mpath=[] print '\tAll paths:',paths for path in paths: t=sum(graph[i][j] for i,j in zip(path,path[1::])) print '\t\tevaluating:',path, t if t<mt: mt=t mpath=path e1=' '.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::])) e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::]))) print 'Best path: '+e1+' Total: '+e2+'\n' if __name__ == "__main__": graph = {'D1': {'D2':1, 'C1':1}, 'D2': {'C2':1, 'D1':1}, 'C1': {'C2':1, 'B1':1, 'D1':1}, 'C2': {'D2':1, 'C1':1, 'B2':1}, 'B1': {'C1':1, 'B2':1}, 'B2': {'B1':1, 'A2':1, 'C2':1}, 'A2': {'B2':1, 'A1':1}, 'A1': {'A2':1}} min_path(graph,'D1','A1')

Prints:

All paths: [['D1', 'C1', 'C2', 'B2', 'A2', 'A1'], ['D1', 'C1', 'B1', 'B2', 'A2', 'A1'], ['D1', 'D2', 'C2', 'C1', 'B1', 'B2', 'A2', 'A1'], ['D1', 'D2', 'C2', 'B2', 'A2', 'A1']] evaluating: ['D1', 'C1', 'C2', 'B2', 'A2', 'A1'] 5 evaluating: ['D1', 'C1', 'B1', 'B2', 'A2', 'A1'] 5 evaluating: ['D1', 'D2', 'C2', 'C1', 'B1', 'B2', 'A2', 'A1'] 7 evaluating: ['D1', 'D2', 'C2', 'B2', 'A2', 'A1'] 5 Best path: D1->C1:1 C1->C2:1 C2->B2:1 B2->A2:1 A2->A1:1 Total: 5

If you change the number in the dict (in this case, all 1 for same cost) that will change the 'cost' of using that segment of the path. There is an example using train routes.