Implementation Dijkstra algorithm in Python

Question

I am implementing Dijkstra’s algorithm in a graph, but it returns only the first call to the function. Even if I call again there is no return, does anyone know why? Follows the code:

def Dijkstra2(self, source, dest):
    shortestDist = {}
    predecessor = {}
    infinity = float('inf')
    path = []

    for node in self.graph:
        shortestDist[node] = infinity

    shortestDist[source] = 0

    while self.graph:
        minNode = None
        for node in self.graph:
            if minNode is None:
                minNode = node
            elif shortestDist[node] < shortestDist[minNode]:
                minNode = node

        for childNode, weight in self.graph[minNode]:
            if (self.hasVertex(childNode) == True):
                weight = int(weight)
                if weight + shortestDist[minNode] < shortestDist[childNode]:
                    shortestDist[childNode] = shortestDist[minNode] + weight
                    predecessor[childNode] = minNode

        self.graph.pop(minNode)

    currentNode = dest

    while currentNode != source:
        try:
            path.insert(0, currentNode)
            currentNode = predecessor[currentNode]
        except KeyError:
            print('Path not reachable')
            break

    path.insert(0, source)

    if (shortestDist[dest] != infinity):

        print('Shortest distance between ', source, ' and ', dest, 'is ' + str(shortestDist[dest]))
        print('The paths is ' + str(path))

    return path

the graph:

graph = {James: {(Larry, 2), (liam, 3)}; Larry: {(James, 1), (paul, 3)}; paul: {(Jim, 2)}}

When I execute:

grafo.Dijkstra2('james', 'paul')
grafo.Dijkstra2('james', 'liam')

returns:

Shortest distance between james and paul is 5
The path is [james, larry, paul]

But the other call does not execute. Where is the error?

Answer 1

I believe that’s when you perform self.graph.pop(minNode) that is removing the node from the graph, so in the second execution the graph is empty and ends up returning nothing.

You can do a test by putting one if at the beginning of the method that prints something if the graph is empty.