path - Djikstra 的最短路径实现中的奇怪错误

Question

我正在尝试为没有负边的加权无向图实现到所有节点的单源最短路径的 Djikstra 算法。代码如下：

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。有人可以指出我的代码中的算法错误吗？

标签： pathimplementationshortest