python – 列车路线的最佳数据结构？

假设您有100个停靠点和多个非字母和非数字路线.想想巴黎地铁：

现在尝试使用直接的Python dict来计算FDR和La Fourche之间的时间？这涉及两个或更多不同的路线和多个选项.

tree或某种形式的graph是更好的结构.对于1对1的映射,dict非常棒;树对于彼此相关的节点的丰富描述更好.然后,您将使用类似Dijkstra’s Algorithm的东西进行导航.

由于nested dict of dicts or dict of lists是一个图表,很容易想出一个递归的例子：

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,path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths       

def min_path(graph,end):
    paths=find_all_paths(graph,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 'ttevaluating:',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,mpath[1::])))
    print 'Best path: '+e1+'   Total: '+e2+'n'  

if __name__ == "__main__":
    graph = {'A': {'B':5,'C':4},'B': {'C':3,'D':10},'C': {'D':12},'D': {'C':5,'E':9},'E': {'F':8},'F': {'C':7}}
    min_path(graph,'A','E')
    min_path(graph,'D')
    min_path(graph,'F')

打印：

All paths: [['A','C','D','E'],['A','B','E']]
        evaluating: ['A','E'] 25
        evaluating: ['A','E'] 29
        evaluating: ['A','E'] 24
Best path: A->B:5 B->D:10 D->E:9   Total: 24

    All paths: [['A','D'],'D']]
        evaluating: ['A','D'] 16
        evaluating: ['A','D'] 20
        evaluating: ['A','D'] 15
Best path: A->B:5 B->D:10   Total: 15

    All paths: [['A','E','F'],'F']]
        evaluating: ['A','F'] 33
        evaluating: ['A','F'] 37
        evaluating: ['A','F'] 32
Best path: A->B:5 B->D:10 D->E:9 E->F:8   Total: 32