C ++无限循环中的Dijkstra算法
Dijkstra's algorithm in c++ infinite loop
我试图用 C++ 实现 Dijkstras 的算法。现在我在调试时遇到了麻烦。在我的代码中某处有一个无限循环。我的图形实现很糟糕。如果您有任何想法我的代码有什么问题,即使它不是关于主要问题,请告诉我。
我不需要其他人的代码,我需要它作为我的代码但已修复,这样我就可以找到我在代码中的错误并更好地理解它(我只理解我的代码,遗憾的是 C++ 编译器不理解)。
这是我的代码:
#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
vector < vector<int> > graf;
int fromnode, tonode;
struct nodeinfo
{
//this contains info about a node
bool visited = 0;
int dis = INT_MAX/2;
};
nodeinfo sample;
vector<nodeinfo> info; // if visited
queue<int> togo;
// dijkstra algorithm
void dijkstra(int currnode)
{
//visited current node
info[currnode].visited = 1;
//go see every node connected to the current one
for(int i = 0; i < graf[currnode].size(); i ++){
if (graf[currnode][i] != INT_MAX/2 ) {
// if visited push to queue and check distance
if(info[i].visited== 0)
togo.push(i);
info[i].dis = max(info[i].dis,info[currnode].dis + graf[currnode][i]);
}
}
}
int main()
{
//input n
int n;
cin >> n;
//declaring variables
graf.resize(n*2);
info.resize(n*2);
vector<int> fillin (100,INT_MAX/2);
graf.insert(graf.begin(),100,fillin);
int a,b,c;
//input in graphinfo[graf[currnode][i
for(int i = 0; i < n; i ++){
cin >> a >> b >> c;
if (graf[a][b] > c)
graf[a][b] = graf[b][a] = c;
cout << i << endl;
}
// input from witch node to go and where to go and
cin >> fromnode >> tonode;
info[fromnode].dis = 0;
togo.push(fromnode);
//dijkstra start
while(!togo.empty()){
dijkstra(togo.front());
}
// output
cout << info[tonode].dis << endl;
return 0;
}
在我使用此输入将 cout << "at node " << currnode << endl;
放在 dijskstra 函数的开头之后:
卡在节点 1 上:
你的循环说
while(!togo.empty())
但您从未从 togo
中删除任何内容。
你会想 pop
在一个合适的地方。
(找一个合适的地方留下作为练习。)