Java A* Implementation results in two connecting nodes

Vote count:

0

I tried to search google and stackoverflow for similar questions but I wasn't successful in finding any.

My implementation of A* works, however when collecting the path from the start node to the end node it simply loops through two nodes which are connected to each other (I can get from node A to node B but also from node B to node A).

I've followed wikipedia's A* implementation but also when I created Dijksta's algorithm it uses the same method which worked perfectly - so I'm confused as to why this is not.

My current output is this:

Node: 3093, 
Node: 3085, 
Node: 3093, 
Node: 3085, 
Node: 3093, 
Node: 3085, 
Node: 3093, 
... repeated

Here is my A* algorithm implementation

private Vertex dijkstra (int startLoc, int endLoc)
  {         
      Vertex startLocation = pqTemp.removeVertex(startLoc);      
      int y = 0;
      Vertex endLocation = pqTemp.QueueArray[y];
      while (endLocation.city != endLoc)
      {
          y++;
          endLocation = pqTemp.QueueArray[y];          
      }      

      startLocation.setTentativeDistance(0);      
      startLocation.setH(heuristic(endLocation, startLocation)); 
      startLocation.setF(startLocation.getH() + startLocation.getTentativeDistance());

      pqOpen.AddItem(startLocation);       
       while (!(pqOpen.IsEmpty()))
       {
           currentNode = pqOpen.GetNextItem();

           if (currentNode == null || currentNode.getTentativeDistance() == Double.POSITIVE_INFINITY)
           {
               return null;
           }
           else if (currentNode.city == endLoc)
           {
               return currentNode;
           }           
           else
           {
              pqClosed.AddItem(currentNode);

              while (currentNode.neighbors.GetNoOfItems() > 0) //for each neighbor of currentNode
              {         
                    Edge hold = (Edge)currentNode.neighbors.GetItem(0); 
                    currentNode.neighbors.DeleteItem(0);
                    int x = 0;
                    //gets the neighbor(Edge) into currentNodeUnvisited(Vertex)
                    Vertex currentNodeUnvisited = pqTemp.QueueArray[x];                    
                    while (x < pqTemp.GetQueueSize()&& hold.toid != currentNodeUnvisited.city)
                    {
                        currentNodeUnvisited = pqTemp.QueueArray[x]; 
                        x++;
                    }                    

                    //if the neighbor is in closed set, move to next neighbor
                    for(int z = 0; z < pqClosed.GetQueueSize() == false; z++)
                    {
                        if (pqClosed.QueueArray[z].city == currentNodeUnvisited.city)
                        {
                            break;
                        }                         
                    }  

                    double temp_g_score = (currentNode.getTentativeDistance() + hold.distance);

                    //checks if neighbor is in open set
                    boolean foundNeighbor = false;
                    int z;
                    for(z = 0; z < pqOpen.GetQueueSize() && foundNeighbor == false; z++)
                    {
                        if (pqOpen.QueueArray[z].city == currentNodeUnvisited.city)
                        {
                            foundNeighbor = true;
                        }  
                    }

                    if (!(foundNeighbor) || temp_g_score < currentNodeUnvisited.getTentativeDistance())                        
                    {  
                        currentNodeUnvisited.from = currentNode;
                        edgeResult.AddItem(hold);
                        currentNodeUnvisited.setTentativeDistance(temp_g_score);
                        currentNodeUnvisited.setH(heuristic(endLocation, currentNodeUnvisited));
                        currentNodeUnvisited.setF(currentNodeUnvisited.getH() + currentNodeUnvisited.getTentativeDistance());  

                        if (!(foundNeighbor)) // if neighbor isn't in open set, add it to open set
                        {    

                            pqOpen.AddItem(currentNodeUnvisited);                            
                        }  

                    }  
                }            
          }                          
      } 
     return null;
  }

Does anyone know why it doesn't properly store the .from? Also I'm wanting to store the edges that the program traversed to get the successful route - does anyone know how I'd do that? Can I simply implement a storage that will add the correct edge?

asked 58 secs ago

Craig

135

Java A* Implementation results in two connecting nodes