Python - Dijsktra 's Algorithm 거리 문제

Question

코드에 문제가 발생했습니다. 시작 노드에서 노드까지의 거리를 계산할 수 없습니다. ,

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8 : 나는 형식의 텍스트 파일이 9

이것은 그래프의 노드 거리를 나타냅니다. 불행히도, 몇 가지 다른 방법을 시도 함에도 불구하고 여전히 다양한 오류 메시지가 계속 발생합니다.

infinity = 1000000 
invalid_node = -1 
startNode = 0 

class Node: 
     distFromSource = infinity 
     previous = invalid_node 
     visited = False 

def populateNodeTable(): 
    nodeTable = [] 
    index =0 
    f = open('route.txt', 'r') 
    for line in f: 
     node = map(int, line.split(',')) 
     nodeTable.append(Node()) 
     print nodeTable[index].previous 
     print nodeTable[index].distFromSource 
     index +=1 

    nodeTable[startNode].distFromSource = 0 

    return nodeTable 

def tentativeDistance(currentNode, nodeTable): 
    nearestNeighbour = [] 
    for currentNode in nodeTable: 
#  if Node[currentNode].distFromSource + currentDistance = startNode + currentNode 
#  currentDistance = currentNode.distFromSource + nodeTable.currentNode 
     currentNode.previous = currentNode 
     currentNode.length = currentDistance 
     currentNode.visited = True 
     currentNode +=1 
     nearestNeighbour.append(currentNode) 
     print nearestNeighbour 

    return nearestNeighbour 

def shortestPath (nearestNeighbour) 
    shortestPath = [] 
    f = open ('spf.txt', 'r') 
    f.close() 

currentNode = startNode 

if __name__ == "__main__": 
    populateNodeTable() 
    tentativeDistance(currentNode,populateNodeTable()) 

내 tentativeDistance 기능에서 '#'으로 시작하는 줄은 문제가되는 부분입니다. 그들은 나를 혼동스럽게하지만 웹상에서 다른 구현물을 보았습니다.

Answer 1

저는 몇 달 전에 Dijkstra 's Algorithm을 Python으로 프로그래밍했습니다. 자사의 테스트 및 작동한다 :

def dijkstra(u,graph): 
    n = graph.numNodes 
    l = { u : 0 } ; W = graph.V() 
    F = [] ; k = {} 
    for i in range(0,n): 
     lv,v = min([ (l[lk],lk) for lk in l.keys() if lk in W ]) 
     W.remove(v) 
     if v!=u: F.append(k[v]) 
     for v1 in [ v2 for v2 in graph.G(v) if v2 in W ]: 
     if v1 not in l or l[v]+graph.w(v,v1) < l[v1]: 
      l[v1] = l[v] + graph.w(v,v1) 
      k[v1] = (v,v1) 
    return l,F 

당신은 w (그래프 노드를 산출) 방법 V()와 클래스 그래프 필요 (v1이, V2) ((V1, V2 가장자리의 무게를 산출하는 노드의 v를 산출하는 G (v)와 numNodes 속성을 제거한다.