Алгоритм Дейкстры не работает

Question

Алгоритм Дейкстры не работает

Я создаю игру для школьного проекта и хочу использовать алгоритм Дейкстры как часть ИИ для объектов, от которых игрок должен увернуться.

Итак, у меня есть график (матрица смежности), и я хочу использовать 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 это начальный узел.

Кто-нибудь знает, что я делаю не так?

0

algorithm c++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);
}
}
}

1

Источник

Accepted Answer

В алгоритме Дейкстры вы отмечаете как посещенный только узел, на который указывает кратчайший путь увеличения. Я вижу ошибку, которую вы делаете здесь:

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

Не отмечайте узлы как посещенные немедленно.

Пометить как посещенный только узел u будет указывать после цикла

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

В противном случае для каждого улучшения вы будете отмечать узел как посещенный, даже не обрабатывая их все.

3