3

我理解这样的简单有向图解释：

graph = {1: [2], 2: [3], 3: [4, 5, 1], 4: [], 5: [4]}
#               1
#              / .
#             /   \
#            .     \
#       4--.3 ------.2
#        \  .
#         \ |
#          .5

但是不知道dict的dict怎么解释，比如：

{1: {2: 3, 3: 8, 5: -4}, 2: {4: 1, 5: 7}, 3: {2: 4}, 4: {1: 2, 3: -5}, 5: {4: 6}}

是加权图吗？我应该如何理解这种图表的写法？

如果您决定否决这个问题，请在评论中留下相应文章的链接。

4

2 回答 2

6

是的，这是一个带有加权边的有向图。下图

加权有向图

表示为..

L = {'A': {'C':2, 'D':6}, 'B': {'D':8, 'A':3},
   'C': {'D':7, 'E':5}, 'D': {'E':-2}, 'E': {}}
于 2013-06-02T16:04:22.263 回答
2

这是一个加权边有向图。您还可以使用graphviz来可视化您的特定数据：

nestedg={1: {2: 3, 3: 8, 5: -4}, 
     2: {4: 1, 5: 7}, 
     3: {2: 4}, 
     4: {1: 2, 3: -5}, 
     5: {4: 6}}

with open('/tmp/graph.dot','w') as out:
    for line in ('digraph G {','size="16,16";','splines=true;'):
        out.write('{}\n'.format(line))  
    for start,d in nestedg.items():
        for end,weight in d.items():
              out.write('{} -> {} [ label="{}" ];\n'.format(start,end,weight))
    out.write('}\n')

这产生了这个图形表示：

在此处输入图像描述

您可以使用Dijkstra 算法之类的东西来导航路径。一个示例用途是使用具有更大“成本”的某些路由进行路由：

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 from {} to {}: {}'.format(start,end,paths)
    for path in paths:
        t=sum(graph[i][j] for i,j in zip(path,path[1::]))
        print '\t\tevaluating: {}, cost: {}'.format(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__":
    nestedg={1: {2: 3, 3: 8, 5: -4}, 
         2: {4: 1, 5: 7}, 
         3: {2: 4}, 
         4: {1: 2, 3: -5}, 
         5: {4: 6}}

    min_path(nestedg,1,5)
    min_path(nestedg,1,4)
    min_path(nestedg,2,1)

使用您的数据，通过图表的一些示例路线是：

    All paths from 1 to 5: [[1, 2, 5], [1, 3, 2, 5], [1, 5]]
        evaluating: [1, 2, 5], cost: 10
        evaluating: [1, 3, 2, 5], cost: 19
        evaluating: [1, 5], cost: -4
Best path: 1->5:-4   Total: -4

    All paths from 1 to 4: [[1, 2, 4], [1, 2, 5, 4], [1, 3, 2, 4], [1, 3, 2, 5, 4], [1, 5, 4]]
        evaluating: [1, 2, 4], cost: 4
        evaluating: [1, 2, 5, 4], cost: 16
        evaluating: [1, 3, 2, 4], cost: 13
        evaluating: [1, 3, 2, 5, 4], cost: 25
        evaluating: [1, 5, 4], cost: 2
Best path: 1->5:-4 5->4:6   Total: 2

    All paths from 2 to 1: [[2, 4, 1], [2, 5, 4, 1]]
        evaluating: [2, 4, 1], cost: 3
        evaluating: [2, 5, 4, 1], cost: 15
Best path: 2->4:1 4->1:2   Total: 3
于 2013-06-02T17:23:00.213 回答