0

コードで問題が発生しました。開始ノードからノードまでの距離を計算できません。次の形式のテキスト ファイルがあります。

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関数の「#」で始まる行は、私に問題を引き起こすセクションです. 私は混乱していますが、ウェブ上の他のいくつかの実装を見てきました

4

1 に答える 1

0

私は数ヶ月前に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

メソッド V() (グラフ ノードを生成する)、w(v1,v2) (エッジの重み (v1,v2) を生成する)、remove (グラフからエッジを削除する)、およびメソッドを持つクラス Graph が必要です。属性 numNodes (グラフ内のノードの数を生成) および G(v) はノード v の近傍を生成します。

于 2011-03-08T21:08:18.617 に答える