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)

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.


Need Your Help

Convert UIImage to uint8 array: iOS

ios uiimage bytearray aes

Can we convert an UIImage to uint8 byte array?

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

hibernate grails servlet-filters

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...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.