C ++无限循环中的Dijkstra算法

Question

我试图用 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 上：

Answer 1

你的循环说

while(!togo.empty())

但您从未从 togo 中删除任何内容。
你会想 pop 在一个合适的地方。
（找一个合适的地方留下作为练习。）

C ++无限循环中的Dijkstra算法

Dijkstra's algorithm in c++ infinite loop

c++

algorithm

dijkstra