我的Dijkstra算法有什麼問題

Question

它返回值（21,2,0，-1，-1等），因爲它實際上只應該返回原點和目標，因爲它們之間有一條清晰的路徑。我無法理解我做錯了什麼。 注意：代碼只是將最接近的節點返回到原點（尋路對象），然後是目標（0），而不考慮原點的位置。 更新：無論該特定路徑是否受阻，新代碼（現在在下面顯示的代替其他代碼）只是將目標節點作爲序列中的下一個返回。

def Dijkstra(NodeDistanceApart, Target): 
    #finds the shortest path according to node distances 


    #0 - Initializes values for pathfinding 
    NodeDistanceFromOrigin = [10000.0] * NUMBEROFNODES 
    NodeSolved = [False] * NUMBEROFNODES 
    NodeArcSet = [[-1] * NUMBEROFNODES for x in range(NUMBEROFNODES)] 
    ClosestNode = 0 
    PreviousNode = 0 

    #1 - Sets the origin node (the NPC node) and the target node (the player node) values 
    NodeSolved[NUMBEROFNODES2] = True 
    NodeDistanceFromOrigin[NUMBEROFNODES2] = 0 
    NodeArcSet[NUMBEROFNODES2][0] = NUMBEROFNODES2 

    #2 - finds the shortest path 
    while NodeSolved[0] == False: 
     ClosestNode = 0 
     for n in range(NUMBEROFNODES): 
      if NodeSolved[n] == True:#loops through nodes, if a node is solved, find connected nodes 
       for i in range(NUMBEROFNODES): 
        if NodeSolved[i] == False and NodeDistanceApart[n][i] < 10000:#loops through nodes, if a node is solved or unconnected, then ignore it 
         if (NodeDistanceFromOrigin[n] + NodeDistanceApart[n][i]) < NodeDistanceFromOrigin[i]: 
          NodeDistanceFromOrigin[i] = NodeDistanceFromOrigin[n] + NodeDistanceApart[n][i] 
         if NodeDistanceFromOrigin[i] < NodeDistanceFromOrigin[ClosestNode]: 
          ClosestNode = i 
          PreviousNode = n 
     NextInArray = -1 
     n = 0 
     while NextInArray == -1:#finds the next unused index in the array for a nodes arc set 
      if NodeArcSet[ClosestNode][n] == -1: 
       NextInArray = n 
      n = n + 1 
     NodeSolved[ClosestNode] = True 
     NodeArcSet[ClosestNode] = NodeArcSet[PreviousNode] 
     NodeArcSet[ClosestNode][NextInArray] = ClosestNode 
    print(NodeArcSet[0]) 
    return NodeArcSet 

Answer 1

我沒有讀完整個算法，因爲執行時存在嚴重錯誤。

問題是這樣的線

NodeArcSet = [[-1] * NUMBEROFNODES] * NUMBEROFNODES 

這產生NUMBEROFNODES指針相同的數組[[-1] * NUMBEROFNODES]。

>>> a=[[0]*2]*2 
>>> a 
[[0, 0], [0, 0]] 
>>> a[0][0]=1 
>>> a 
[[1, 0], [1, 0]] 

我做些什麼來解決這個問題是一樣的東西

NodeArcSet = [[-1] * NUMBEROFNODES for x in xrange(NUMBEROFNODES)] 
        # In python 3 you should use range instead of xrange.