In the graph class, I had made a vertList dictionary which stores vertex name and vertex class object, the dictionary which throws key error 0 in relax function when calling in Dijkstra function.

I had tried using get function instead of direct calling from the dictionary itself.

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)

Exception

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'

2 Answers

2
olinox14 On Best Solutions

When you call your relax() method, u is a string, not an integer!

That's whhy you get a KeyError: there is indeed a 0 key, but not '0'.

When you defined the priority queue, you explicitly store strings:

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

Then, in your dijkstra method, you convert this string to an int in your if statement, but not in the graph.relax() call after that:

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

Before making any further debugging, I would check the attribute soruce of the class Graph, which I suppose it is source and you have misstyped it, as the function defined in class Graph getSource returns self.source.getId()