# 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:

1. D1, C1, B1, B2, A2, A1 (RED LINE PATH)
2. D1, C1, C2, B2, A2, A1 (PURPLE LINE PATH)
3. D1, D2, C2, B2, A2, A1 (GREEN LINE PATH)
4. D1, D2, C2, C1, B1, B2, A2, A1 (YELLOW LINE PATH)

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.

### Convert UIImage to uint8 array: iOS

Can we convert an UIImage to uint8 byte array?

### Hibernate session is not open when trying to iterate over myDomain.collection() in Grails application

I'm trying to override a servlet filter provided by the Grails Spring Security Rest plugin (a regular servlet filter, not a Grails filter class) in my Grails application, however I think I'm missin...