Heapq 模块和字典之间的奇怪干扰

Question

一方面，我有一个 grid defaultdict，它存储网格上每个节点的相邻节点及其权重（下例中均为 1）。

        node   (w  nbr_node)
grid = { 0:   [(1, -5), (1, -4), (1, -3), (1, -1), (1, 1), (1, 3), (1, 4), (1, 5)], 
         1:   [(1, -4), (1, -3), (1, -2), (1, 0), (1, 2), (1, 4), (1, 5), (1, 6)], 
         2:   [(1, -3), (1, -2), (1, -1), (1, 1), (1, 3), (1, 5), (1, 6), (1, 7)], 
         3:   [(1, -2), (1, -1), (1, 0), (1, 2), (1, 4), (1, 6), (1, 7), (1, 8)],
        ...
        }

另一方面，我有一个 Djisktra 函数可以计算此网格上 2 个节点之间的最短路径。该算法使用 heapq 模块并且工作得很好。

import heapq

def Dijkstra(s, e, grid): #startpoint, endpoint, grid
    visited = set()
    distances = {s: 0} 
    p = {} 
    queue = [(0, s)] 

    while queue != []:

        weight, node = heappop(queue) 
        if node in visited: 
            continue

        visited.add(node) 

        for n_weight, n_node in grid[node]: 
            if n_node in visited: 
                continue

            total = weight + n_weight 

            if n_node not in distances or distances[n_node] > total: 

                distances[n_node] = total
                heappush(queue, (total, n_node))
                p[n_node] = node

问题：多次调用 Djikstra 函数时，heappush 是...无故在 grid 字典中添加新键！

这是一个 MCVE：

from collections import defaultdict

# Creating the dictionnary
grid = defaultdict(list) 
N = 4
kernel = (-N-1, -N, -N+1, -1, 1, N-1, N, N+1)

for i in range(N*N): 
    for n in kernel:
        if i > N and i < (N*N) - 1 - N and (i%N) > 0 and (i%N) < N - 1:
            grid[i].append((1, i+n))



# Calling Djikstra multiple times
keys = [*range(N*N)]

while keys:

    k1, k2 = random.sample(keys, 2)

    Dijkstra(k1, k2, grid) 

    keys.remove(k1)
    keys.remove(k2)

原grid defaultdict:

dict_keys([5, 6, 9, 10])

...并且多次调用 Djikstra 函数后：

dict_keys([5, 6, 9, 10, 4, 0, 1, 2, 8, 3, 7, 11, 12, 13, 14, 15])

多次调用Djikstra函数时没有heappush（只是在最后注释heappush）：

dict_keys([5, 6, 9, 10])

问题:

我怎样才能避免这种奇怪的行为？

请注意，我使用的是 Python 2.7，无法使用 numpy。

Answer 1

我可以重现并修复。问题在于您构建 grid 的方式：它包含的值不在示例中从 -4 到 0 和从 16 到 20 的键中。所以你把那些不存在的节点推到头上，然后弹出它们。

你最终执行 for n_weight, n_node in grid[node]:，其中 node 不（仍然）存在于 grid 中。由于 grid 是默认字典，因此会自动插入一个新节点，并将空列表作为值。

修复很简单（至少对于示例数据而言）：足以确保所有添加为网格值的节点都作为具有模数的键存在：

for i in range(N*N): 
    for n in kernel:
        grid[i].append((1, (i+n + N + 1)%(N*N)))

但即使对于真实数据，也不难确保网格值中存在的所有节点也存在于键中...

顺便说一句，如果 grid 是一个简单的 dict，错误会立即出现 KeyError on grid[node]。

Heapq 模块和字典之间的奇怪干扰

Strange interferences bewteen Heapq module and dictionary

python

dictionary

python-2.7

heapq