내 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.