Блог

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

 typedef long long ll;
#define vi vector<int> 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define f first
#define s second

using namespace std;

void help(vector<vector<pll> > graph)
{
    vector<ll> dist(n 1,LLONG_MAX);
    dist[0]=0;
    priority_queue< pll, vector <pll> , greater<pll> > pq;
    pq.push(mp(0,0));//dist,v
    vector<bool> visited(n 1,false);
    //printArray(dist);
    while(!pq.empty())
    {

        pii p = pq.top();
        pq.pop();

        if(!visited[p.s])
        {
            visited[p.s] = true;
            dist[p.s]=p.f;
            for(ll i = 0; i<graph[p.s].size(); i  )
            {
                pq.push(mp(graph[p.s][i].s dist[p.s],graph[p.s][i].f));
            }
        }
// if instead of the above if block, I use the below for block, the code gives output!
//        for(auto [v,d]:graph[p.s])
//      {
//          if(dist[v]>dist[p.s] d)
//          {
//              dist[v] = dist[p.s] d;
//              pq.push({dist[v],v});
//          }
            
//      }
        
    }
    
    for(ll i = 1; i <=n; i  )
    {
        cout << dist[i]<< " ";
    }
    cout << "n";
}
 

Реализация довольно проста, но мой код выдает неверные выходные данные, и я не могу понять причину ошибки. Замена блока if и вместо этого установка блока for дает правильный вывод, но я думаю, что оба они по сути являются одним и тем же алгоритмом. Я поддерживаю посещенный массив, и если выскочивший узел u из кучи не посещен, соответствующий ключ является кратчайшим расстоянием до u, и теперь я вставляю новые пары со key = Dist[u] wt(uv) всеми соседями v u . Может ли кто-нибудь указать на алгоритмическую ошибку в моем коде?