5

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)

enter image description here

1

1 Answer 1

10

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.

1
  • I know this answer is 6.5 years old, but this was super helpful. Thank you!
    – Chuck C.
    Commented Feb 23, 2021 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.