迭代给出错误的对列表的向量

Question

我写了下面的代码，但是里面有问题。它没有显示编译器错误，但我得到运行失败。我无法弄清楚逻辑哪里出了问题。

代码是dijkstras算法为每个顶点寻找最短路径。

#include <bits/stdc++.h>

using namespace std;
# define inf 0x3f3f3f3f
typedef pair<int,int> ipair;

class graph
{
    int v;
    vector<list<pair<int,int>>> adj; 
public:
    graph(int v);
    void addedge(int w,int u,int v);
    void shortestpath(int src);
};

graph::graph(int v)
{
    this->v=v;
}

void graph::addedge(int u,int v,int w)
{
    adj[u].push_back(make_pair(v,w));
    adj[v].push_back(make_pair(u,w));
}

void graph::shortestpath(int src)
{
    priority_queue<ipair,vector<ipair>,greater<ipair>> pq; 

    vector<int> dist(v,inf);
    pq.push(make_pair(0,src));
    dist[src]=0;

    while(!pq.empty())
    {
        int m=pq.top().second;
        pq.pop();

        for(pair<int,int>& i:adj[m]) //check this ranged based for loop
        {          

                int p=i.first;
                int pwt=i.second;

                if(dist[p]>dist[m]+pwt)
                {
                dist[p]=dist[m]+pwt;
                pq.push(make_pair(dist[p],p));
                }

        }
    }
    for(int i=0;i<v;++i)
        cout << i << " " << dist[i];

}

int main()
{    
    graph g1(9);
    g1.addedge(0,1,4);
    g1.addedge(0,7,8);
    g1.addedge(1,2,8);
    g1.addedge(1,7,11);
    g1.addedge(2,3,7);
    g1.addedge(2,8,2);
    g1.addedge(2,5,4);
    g1.addedge(3,4,9);
    g1.addedge(3,5,14);
    g1.addedge(4,5,10);
    g1.addedge(5,6,2);
    g1.addedge(6,7,1);
    g1.addedge(6,8,6);
    g1.addedge(7,8,7);
    g1.shortestpath(0);

    return 0;
}

我认为逻辑错误的地方：如您所见，我想创建一个向量> adj，而不是为 adj.so 分配 space，这是错误的还是正确的？如果这是正确的，那么可能会检查我在无效最短路径中使用的基于范围的 for 循环（我已经用注释标记了它），也许那个循环中有问题？有人可以帮我吗？我卡住了。

Answer 1

当你打电话时

adj[u].push_back(make_pair(v,w));

in graph::addedge 元素 adj[u] 不存在，程序崩溃。你得到了超出范围的向量的未定义行为读取元素。您应该在 graph.

的构造函数中创建此向量的 v 个元素

graph::graph(int v)
{
    this->v=v;
    adj.resize(v);   // <---
}

算法看起来不错，结果正确，但打印输出不可读。您应该在 for 循环中添加 endl 以获得更具可读性的结果。

for(int i=0;i<v;++i)
    cout << i << " " << dist[i] << endl;

迭代给出错误的对列表的向量

Iterating over vector of list of pairs giving errors

dijkstra

c++11