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); 

노드를 즉시 방문한 것으로 표시하지 마십시오. 방문으로 그렇지 않으면 모든 개선을위한 노드를 표시합니다주기 후

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

를 가리 킵니다 노드 만 u 방문으로

마크, 심지어 그들 모두를 처리 할 수 ​​없습니다.

Answer 2

Dijkstra 알고리즘처럼 보이지 않습니다. 검색 노드

에지 노드의 정렬 된 목록의

• 목록 :
  는 노드의 두 개의 목록을 관리 할 필요가 익스트라 알고리즘을 구현합니다.
  이 목록의 각 노드에는이 위치에 도달하는 데 드는 비용이 있습니다.

코드에이 목록이 없습니다.

또한 노드에 비용을 저장합니다. 노드에 도달하는 데 드는 비용은 경로에 따라 다르기 때문에 (노드와 관련된 여러 비용을 저장할 수 없다면)이 방법은 효과가 없습니다.

나는 코드는 다음과 같이 기대 :

// 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); 
      } 
    } 
}