Python 字典键错误“0”但字典中有 0

Question

在图表 class 中，我制作了一个 vertList 字典，其中存储顶点名称和顶点 class 对象，该字典在调用 Dijkstra 函数时在 relax 函数中抛出键错误 0。

我曾尝试使用 get 函数而不是直接从字典本身调用。

from collections import defaultdict
import math
import heapq


class PriorityQueue:
    def __init__(self):
        self.is_empty = True
        self.length = 0
        self.pqueue = []

    def makePQueue(self, l):
        self.pqueue = l.copy()
        heapq.heapify(self.pqueue)
        if(len(l) > 0):
            self.length = len(l)
            self.is_empty = False

    def addElement(self, element):
        heapq.heappush(self.pqueue, element)
        self.length = self.length+1

    def removeElement(self):
        if(self.length > 0):
            element = heapq.heappop(self.pqueue)
            self.length = self.length-1
            if(self.length == 0):
                self.is_empty = True
            return element
        else:
            return None


# vertex class

class Vertex:
    def __init__(self, key):
        self.id = key
        self.parent = None
        self.distFromSource = math.inf

    def getId(self):
        return self.id

    def getParent(self):
        return self.parent

    def addParent(self, p):
        self.parent = p

    def getDistSource(self):
        return self.distFromSource

    def setDistFromSource(self, d):
        self.distFromSource = d

# Graph class


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
        self.soruce = None
        self.vertList = {}

    def addVertex(self, v):

        if(v not in list(self.vertList.keys())):
            ver = Vertex(v)
            self.vertList[v] = ver

    def addEdge(self, u, v, c):
        if(u not in list(self.vertList.keys())):
            ver = Vertex(u)
            self.vertList[u] = ver
        if(v not in list(self.vertList.keys())):
            ver = Vertex(v)
            self.vertList[v] = ver
        self.graph[u].append((v, c))

    def getWeight(self, u, v):
        # binary search can be implemented for speed
        for i in self.graph[u]:
            if(i[0] == v):
                return i[1]

    def setSource(self, s):
        if(s not in list(self.vertList.keys())):
            ver = Vertex(s)
            self.vertList[s] = ver
        self.vertList[s].setDistFromSource(0)
        self.source = self.vertList[s]
        self.source.setDistFromSource(0)

    def getSource(self):
        return self.source.getId()

    def getDistList(self):
        l = [(self.vertList[i].getDistSource(), str(i))
             for i in list(self.vertList.keys())]
        return l

    # def costArray(self):
        # l = [i.]
    # implementation of edge array of cost

    def relax(self, u, v, c):
        if(self.vertList[v].getDistSource() > self.vertList[u].getDistSource()+c):
            self.vertList[v].setDistFromSource(
                self.vertList[u].getDistSource()+c)
            self.vertList[v].addParent(self.vertList[u])


def dijkstra(graph):
    ss = []
    l = graph.getDistList()
    pq = PriorityQueue()
    pq.makePQueue(l)
    # print(pq.pqueue)
    while(pq.is_empty == False):
        (cost, u) = pq.removeElement()
        # in priority queue on the basis of cost
        if int(u) not in ss:
            ss = ss.append(int(u))
            for (i, c) in graph.graph[int(u)]:
                graph.relax(u, i, c)
```

g = Graph()

g.addEdge(0, 1, 3)

g.addEdge(0, 2, 2)

g.addEdge(0, 3, 5)

g.addEdge(1, 0, 3)

g.addEdge(1, 4, 3)

g.addEdge(4, 1, 3)

g.addEdge(4, 2, 1)

g.addEdge(4, 6, 4)

g.addEdge(2, 0, 2)

g.addEdge(2, 4, 1)

g.addEdge(2, 5, 6)

g.addEdge(3, 0, 5)

g.addEdge(3, 5, 2)

g.addEdge(5, 2, 6)

g.addEdge(5, 3, 2)

g.addEdge(5, 6, 1)

g.addEdge(5, 7, 4)

g.addEdge(6, 4, 4)

g.addEdge(6, 5, 1)

g.addEdge(6, 7, 2)

g.addEdge(7, 5, 4)

g.addEdge(7, 6, 2)

g.setSource(0)

dijkstra(g)

异常

python graph.py

Traceback (most recent call last):

  File "graph.py", line 155, in <module>

    dijkstra(g)

  File "graph.py", line 126, in dijkstra

    graph.relax(u, i, c)

  File "graph.py", line 108, in relax

    if(self.vertList[v].getDistSource() > 

self.vertList[u].getDistSource()+c):

KeyError: '0'

Answer 1

当您调用 relax() 方法时，u 是一个字符串，而不是整数！

这就是您得到 KeyError 的原因：确实有一个 0 键，但没有 '0'。

当您定义优先级队列时，您显式存储了字符串：

def getDistList(self):
    l = [(self.vertList[i].getDistSource(), str(i))
         for i in list(self.vertList.keys())]
    return l

然后，在您的 dijkstra 方法中，您在 if 语句中将此字符串转换为 int，但之后的 graph.relax() 调用中则不会：

if int(u) not in ss:
    ss = ss.append(int(u))
    for (i, c) in graph.graph[int(u)]:
        graph.relax(u, i, c)

Python 字典键错误“0”但字典中有 0

Python dictionary key error '0' but 0 is in dictionary

python

dictionary

graph

dijkstra

python-3.x