Estou implementando o algoritmo de Dijkstra em um grafo, porém ele me retorna apenas a primeira chamada à função. Mesmo que eu chame novamente não há retorno, alguém sabe dizer o motivo? Segue o código:
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
o grafo:
grafo = {james: {(larry, 2), (liam, 3)}; larry: {(james, 1), (paul, 3)}; paul: {(jim, 2)}}
Quando executo:
grafo.Dijkstra2('james', 'paul')
grafo.Dijkstra2('james', 'liam')
retorna:
Shortest distance between james and paul is 5
The path is [james, larry, paul]
Mas a outra chamada não executa. Onde está o erro?