Dijkstra的算法不起作用

我正在为一个学校项目创建一个游戏，并且我想使用Dijkstra的算法作为玩家需要躲闪的对象的AI的一部分。Dijkstra的算法不起作用

所以我有一个图表（邻接矩阵），我想用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是开始节点。

有谁知道我在做什么错？

来源

2013-01-03 Bjorn

有通过它与加强调试一个简单的测试案例？ – StoryTeller

更适合[代码审查]（http://codereview.stackexchange.com）然后在这里。至少部分地尝试纠正你的问题（我的意思是**问题**而不是代码）中的错误。 –

我创造了一个方形图形由4 4的大小，我检查，如果该图是在不同的大小正确并产生完美的曲线，但在4×4仍然没有工作，我会espect，我有使用[链接] http://en.wikipedia.org/wiki/Dijkstra's_algorithm [/ link]上的伪代码作为指导 – Bjorn

在Dijkstra算法中，您标记为仅访问最短增广路径指向的节点。我可以看到您在此处发生的错误：

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

不要将节点标记为立即访问。因为用户只访问节点u将指向循环后

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

否则，对于每一个改进的访问，你将迎来节点

马克，甚至不处理他们。

来源

2013-01-03 09:29:00

谢谢，你的答案我已经得到它的工作。我需要将visited和numberVisited的增量放在for之外。 – Bjorn

，它甚至没有像Dijkstra算法。

要实现的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); 
      } 
    } 
}

来源

2013-01-03 09:44:24

Dijkstra的算法不起作用

回答

相关问题