Dijkstra's algorithm not working

0
votes

I'm creating a game for a school project, and I want to use Dijkstra's algorithm as part of an AI for the objects the player needs to dodge.

So I have a graph (an adjacency matrix) and I want to use Dijkstra to get the path from each object to the player, but right now when I call the algorithm, it will not find the player if the player comes after the object.

In my understanding, Dijkstra's algorithm should visit all of the nodes until it finds the destination, but it doesn't in my case.

Here's what my algorithm looks like so far:

Node* Graph::DijkstrasAlgorithm(Node* sNode, Node* dNode){
    std::cout<<"Hello Dijkstra!!"<<std::endl;
    for(unsigned int i = 0; i < this->nodeList.size(); ++i){
        nodeList.at(i)->setDistance(INT_MAX);
        nodeList.at(i)->setVisited(false);
    }
    std::cout<<"everything is set"<<std::endl;
    sNode->setDistance(0);
    int numberVisited = 0;
    Node* u = new Node();
    std::cout<<"before while lus"<<std::endl;
    while(numberVisited < numberOfNodes){
        u->setDistance(INT_MAX);
        for(unsigned int j = 0; j < this->nodeList.size(); ++j){
            if((u->getDistance() > this->nodeList.at(j)->getDistance()) && !this->nodeList.at(j)->isVisited() ){
                u = this->nodeList.at(j);
                u->setVisited(true);
                numberVisited++;
            }
        }

    std::cout<<u->getNodeName()<<"=="<<dNode->getNodeName()<<std::endl;
        if((u == dNode) || (u->getDistance() == INT_MAX)){
            std::cout<<"true"<<std::endl;
            break;
        }


        for(int k = 0; k < u->numberOfneighbors(); ++k){
            if(!u->getNeighbors(k)->isVisited())
            {
            //  std::cout<<u->getDistance()<<std::endl;
                int alt = u->getDistance() + 1;
                if( alt < u->getNeighbors(k)->getDistance()){
                     u->getNeighbors(k)->setDistance(alt);
                     u->getNeighbors(k)->setPrevious(u);
                }
            }
        }

    }
    std::vector<Node* > stack;
    u = dNode;
    while(u->getPrevious() != NULL){
        stack.insert(stack.begin(), u);
        u = u->getPrevious();
    }
    if(!stack.empty())
        return stack.at(0);
    else
        return sNode;


}

In this case, dNode is the destination node, and sNode is the start node.

Does anyone know what I'm doing wrong?

2
c++algorithmdijkstra
Have stepped through it with a debugger on a simple test case? - StoryTeller - Unslander Monica
Better suited for codereview then here. Also try to correct the mistakes in your question(I mean the question not the code) at least partially. - Ivaylo Strandjev
i had created a square graph with size of 4 by 4, i checked if the graph was correct on different sizes and the graph is generated perfect, but on the 4 by 4 it still doesn't work as i would espect, i have used the pseudo code at [link]en.wikipedia.org/wiki/Dijkstra's_algorithm[/link] as a guide line - Bjorn
@Bjorn I've tried my best to clean up this question; can you clarify what you mean by "player comes after the object"? - atomicinf
@izomorphius: codereview only accepts questions about working code. If it was asked there they would send it back here to get fixed before they review it. - Martin York

2 Answers

3
votes

In Dijkstra algorithm you mark as visited only the node to which the shortest augmenting path points to. I can see an error you make here:

u = this->nodeList.at(j);
u->setVisited(true);

Don't mark the nodes as visited immediately.

Mark as visited only the node u will point to after the cycle

for(unsigned int j = 0; j < this->nodeList.size(); ++j){

Otherwise for every improvement you will mark the node as visited, not even processing all of them.

1
votes

It does not even look like Dijkstra algorithm.

To implement Dijkstra algorithms you need to maintain two lists of nodes:

  • A list of searched nodes
  • A SORTED list of edge nodes.
    Each node in this list has the cost to reach this location.

I see neither of these lists in your code.

You are also storing the cost in the node. This will not work as the cost to reach a node will depend on the route (unless you can store multiple costs associated with node).

I would expect the code to look like this:

 // pseudo code.
 // Note all features used are strictly available
 //
 Node* Graph::DijkstrasAlgorithm(Node* sNode, Node* dNode)
 {
     std::list<Node*>                    searchedNodes;
     std::list<std::pair<Node*, cost>>   edgeNodes;

     edgeNodes.push_sorted(sNode, 0);

     while(!edgeNodes.empty())
     {
          std::pair<Node*, cost>  next = edgeNodes.pop_front();
          searchedNodes.push_back(next.first);

          if (next.first == dnode)
          {   // We found the route
              return STUFF;
          }

          for(Edge* edge, next.first->getEdges())
          {
              if (searchedNodes.find(edge->dst) != searchedNodes.end())
              {   continue;
              }

              edgeNodes.push_sorted(dest.dst, next.second + edge->cost);
          }
     }
 }