Алгоритм Дейкстры не работает
Я создаю игру для школьного проекта и хочу использовать алгоритм Дейкстры как часть ИИ для объектов, от которых игрок должен увернуться.
Итак, у меня есть график (матрица смежности), и я хочу использовать 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 это начальный узел.
Кто-нибудь знает, что я делаю не так?
Решение
В алгоритме Дейкстры вы отмечаете как посещенный только узел, на который указывает кратчайший путь увеличения. Я вижу ошибку, которую вы делаете здесь:
u = this->nodeList.at(j);
u->setVisited(true);
Не отмечайте узлы как посещенные немедленно.
Пометить как посещенный только узел u будет указывать после цикла
for(unsigned int j = 0; j < this->nodeList.size(); ++j){
В противном случае для каждого улучшения вы будете отмечать узел как посещенный, даже не обрабатывая их все.
Другие решения
Это даже не похоже на алгоритм Дейкстры.
Для реализации алгоритмов Дейкстры вам нужно поддерживать два списка узлов:
- Список найденных узлов
- Сортированный список краевых узлов.
У каждого узла в этом списке есть стоимость, чтобы достигнуть этого местоположения.
Я не вижу ни одного из этих списков в вашем коде.
Вы также храните стоимость в узле. Это не будет работать, так как стоимость достижения узла будет зависеть от маршрута (если вы не можете сохранить несколько затрат, связанных с узлом).
Я ожидаю, что код будет выглядеть так:
// 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);
}
}
}