CODEWITHSUNDEEP
pythondictionarygraphnodesfloyd-warshall
sicter
sicter

Reputation: 147

Key Error when computing node distances in graph

I keep getting this key error, and I cannot understand how. I am using a for-in statement, so the keys definitely exist:

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)

The error:

Traceback (most recent call last):
File "C:/Users/.../prob1.py", line 58, in floydWarshall
    distance[n][k] = graph[n][k]
KeyError: '2'

The key error simply is on whatever key came first in the nodes, changes every time

Upvotes: 2

Views: 1024

Answers (2)

W.P. McNeill
W.P. McNeill

Reputation: 17056

This looks like the expected behavior to me. Your graph dictionary is not a complete matrix. For example, graph[1] does not contain a key 3.

It looks like you want to have a default infinity value when graph[n][m] does not contain an edge from n to m. You could do this by putting in an explicit check, or using a defaultdict.

Upvotes: 0

zehnpaard
zehnpaard

Reputation: 6233

Not all your graph nodes have an edge to all other graph nodes, so iterating through all nodes k on the entire graph with graph[n][k] will cause a KeyError.

Perhaps you want something like:

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

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

Alternatively, if you want to set distance[n][k] to some default value if the edge doesn't exist:

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

    for k in nodes: 
        distance[n][k] = graph[n].get(k, default_value)

default_value is often set to infinity for distances between nodes

Upvotes: 2

Related Questions