如何查找两个图形节点之间的所有路径

Question

如何像下图中那样找到两个图节点之间的所有路径？我尝试使用广度优先搜索（BFS）算法，但虽然它可以找到所有的点，但无法找到从（S）开始到（E）结束的所有路径。我还尝试了深度优先搜索（DFS），该方法更加接近。但是，在应用该策略时，由于存在一个闭合列表，它只能找到一条路径，可能是红线，而且由于紫色和绿色在该区域穿越了闭合列表，这些路径将被忽略。

我想知道如何获取从（S）开始到（E）结束的所有路径。对于下面的情况：

1. D1，C1，B1，B2，A2，A1（红线路径） 2. D1，C1，C2，B2，A2，A1（紫线路径） 3. D1，D2，C2，B2，A2，A1（绿线路径） 4. D1，D2，C2，C1，B1，B2，A2，A1（黄线路径）

请参见上述图片。

- Mark

---

也许之前已经有人回答过了。我指的是这些链接：[https://dev59.com/92kw5IYBdhLWcg3w9vJ-?rq=1] [https://dev59.com/hHRB5IYBdhLWcg3wH0SW?rq=1] - Dornathal

Answer 1

Dijkstra算法（这里是Python版本）非常有效：

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')

输出：

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

如果你改变字典中的数字 (在这种情况下，所有1表示相同的成本)，那么将会改变使用该路径段的“成本”。这里有一个使用火车路线的示例。

- dawg

---

我知道这个答案已经有6.5年的历史了，但是它非常有帮助。谢谢！ - Chuck C.