c++ - Dijkstra 算法无效

Question

我正在为一个学校项目创建一个游戏，我想使用 Dijkstra 算法作为 AI 的一部分来处理玩家需要躲避的对象。

所以我有一个图(一个邻接矩阵)，我想使用 Dijkstra 来获取从每个对象到玩家的路径，但是现在当我调用算法时，如果玩家跟在后面，它将找不到玩家对象。

在我看来，Dijkstra 算法应该访问所有节点，直到找到目的地，但在我的例子中却没有。

到目前为止，这是我的算法的样子:

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;


}

在这种情况下，dNode是目的节点，sNode是起始节点。

有人知道我做错了什么吗？

Answer 1

在 Dijkstra 算法中，您仅将最短增广路径指向的节点标记为已访问。我可以看到你在这里犯的一个错误:

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

不要立即将节点标记为已访问。

仅将节点u在循环后指向的节点标记为已访问

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

否则，对于每次改进，您都会将节点标记为已访问，甚至不会处理所有这些节点。