Алгоритм Дейкстры в бесконечном цикле C++

Question

Я пытался реализовать алгоритм Дейкстры в C++. Теперь у меня проблемы с отладкой. Где-то в моем коде есть бесконечный цикл. И моя реализация графика сосет. если у вас есть идеи, что не так с моим кодом, даже если речь идет не о главной проблеме, скажите мне.

Мне не нужен код elses, мне нужно, чтобы он был моим кодом, но исправлен, поэтому я могу найти свои ошибки в коде и лучше понять его (я только понимаю свои коды, к сожалению, компилятор 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 в подходящем месте.
(Поиск подходящего места в качестве упражнения.)