计算图中节点距离时的关键错误

Question

我一直收到这个关键错误，我不明白怎么回事。我使用的是for in语句，因此键肯定存在：

def floydWarshall(inFile):
    graph = readGraph(inFile)
    print(graph) # = {'0': {'1': 28, '3': 33}, '2': {'3': 50}, '1': {'4': 44, '2': 10}, '3': {'4': 30}, '4': 999999999}
    nodes = graph.keys()
    print(nodes) # = dict_keys(['0', '2', '1', '3', '4'])

    distance = {}

    for n in nodes:
        distance[n] = {}

        for k in nodes:
        distance[n][k] = graph[n][k]

    for k in nodes:
        for i in nodes:
            for j in nodes:
                distance[i][j] = min (distance[i][j], distance[i][k] + distance[k][j])
    printSolution(distance)

错误：

^{pr2}$

密钥错误只是在节点中最先出现的密钥上，每次都会发生变化

Answer 1

在我看来这是意料之中的行为。你的图形字典不是一个完整的矩阵。例如，图[1]不包含键3。在

当graph[n][m]不包含从n到m的边时，您似乎希望有一个默认的无穷大值。您可以通过进行显式检查或使用defaultdict来实现这一点。在

Answer 2

并不是所有的图节点都有一条到所有其他图节点的边，所以用graph[n][k]遍历整个图上的所有节点k将导致KeyError。在

也许你想要这样的东西：

for n in nodes:
    distance[n] = {}

    for k in graph[n]: 
        distance[n][k] = graph[n][k]

或者，如果要将距离[n][k]设置为某个默认值（如果边不存在）：

^{pr2}$

对于节点之间的距离，default_value通常设置为无穷大