CODEWITHSUNDEEP
algorithmsearchpath
Mark
Mark

Reputation: 18244

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)

enter image description here

Upvotes: 5

Views: 9687

Answers (1)

dawg
dawg

Reputation: 104102

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.

Upvotes: 10

Related Questions