Python - Расчет расстояния в Дейкстре

Question

У меня возникли проблемы с определением расстояния каждого узла от начального узла, а точнее с получением какой-либо информации обратно. Я не получаю вывод из своей функции, прикрепленной по следующей ссылке.

#Values to assign to each node
class Node:
     distFromSource = infinity
     previous = invalid_node
     visited = False

#for each node assign default values    
def populateNodeTable(network): 
    nodeTable = []
    index = 0
    f = open('network.txt', 'r')
    for line in f: 
      node = map(int, line.split(',')) 
      nodeTable.append(Node())

      print "The previous node is " ,nodeTable[index].previous 
      print "The distance from source is " ,nodeTable[index].distFromSource 
      index +=1
    nodeTable[startNode].distFromSource = 0 

    return nodeTable

#calculate the distance of each node from the start node
def tentativeDistance(currentNode, nodeTable):
    nearestNeighbour = []
    for currentNode in nearestNeighbour:
      currentDistance == currentNode.distFromSource + [currentNode][nearestNeighbour] #gets current distance from source
      print "The current distance"
      if currentDistance != 0 & currentNode.distFromSource < Node[currentNode].distFromSource:
         nodeTable[currentNode].previous = currentNode
         nodeTable[currentNode].length = currentDistance
         nodeTable[currentNode].visited = True
         nodeTable[currentNode] +=1
         nearestNeighbour.append(currentNode)
         for currentNode in nearestNeighbour:
           print nearestNeighbour

    return nearestNeighbour

Моя логика, по крайней мере, на мой взгляд, правильна; Тем не менее, я не получаю столько, сколько сообщение об ошибке при запуске кода.

Answer 1

Вы устанавливаете nearestNeighbour быть пустым списком, а затем вы перебираете его for currentNode in nearestNeighbour - который ничего не делает, потому что список пуст - и затем вы возвращаетесь из функции.

(Я предполагаю tentativeDistance это функция, которую вы вызываете и ничего не видите.)

Answer 2

Вы должны переосмыслить свой алгоритм разработки. Попробуйте найти определение псевдокода алгоритма Дейкстры и реализовать его в Python. В частности, вы должны подумать о потоке управления в вашей программе.

Возможно, вы захотите взглянуть на этот рецепт поваренной книги для реализации Dijkstra на Python и посмотреть, сможете ли вы его понять.