python - 火车路线的字典最佳数据结构？

Question

所以我的任务是读取一个文件(记事本文件)，该文件包含一系列火车停靠站以及从一站到另一站所需的时间。例如它看起来像:

Stop A     15
Stop B     12
Stop C     9

现在我需要返回并访问这些站点及其时间。我正在考虑读取文件并将其存储为字典。我的问题是，字典是最好的吗？或者是否有其他一些 python 工具会更有用？任何想法将不胜感激!

Answer 1

我会反其道而行之——直截了当的 dict 并不是最好的选择。

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

现在尝试使用直接的 Python 字典来计算 FDR 和 La Fourche 之间的时间？这涉及两条或更多条不同的路线和多种选择。

A tree或某种形式的 graph是一个更好的结构。字典对于 1 到 1 的映射非常有用； tree 更适合对彼此相关的节点进行丰富的描述。然后你会使用类似 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, 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 = {'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,'A','D')
    min_path(graph,'A','F')

打印:

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

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

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