Getting error while implementing Dijkstra's using the C++ STL. Help!

general
,
1

I am using the adjacency list representation but here, the list adjacent to a vertex shall also contain the corresponding weights.

#define ii pair<int,int>
vector< vector<ii> > edge;

There is a segmentation fault at this line I suppose:

edge[u].push_back(pair<int,int>(v,w));

What’s going wrong here? I have referred to the TopCoder tutorial for my implementation.

    #include<iostream>
    #include<vector>
    #include<queue>
    #define ii pair<int,int>
    
    using namespace std;
    
    class Graph
    {
    public:
    
        priority_queue<ii, vector<ii>, greater<ii> > Q;
    
        vector<int> distance;
    
        vector< vector<ii> > edge;
    
        int V;
    
        Graph(int vertices)
        {
            V=vertices;
            distance=vector<int> (V+1, 987654321);
        }
    
        void addEdge(int u, int v, int w)
        {
            edge[u].push_back(pair<int,int>(v,w));
            edge[v].push_back(ii(u,w));
        }
    
        void dijkstra(int source)
        {
            distance[source]=0;
    
            Q.push(ii(source,0));
    
            while(!Q.empty())
            {
                ii top=Q.top();
    
                Q.pop();
    
                int v=top.first,d=top.second;
    
                if(d<=distance[v])
                {
                    for(unsigned int i=0;i<edge[v].size();++i)
                    {
                        int v2=edge[v][i].first;
                        int d2=edge[v][i].second;
    
                        if(distance[v2]>distance[v]+d2)
                        {
                            distance[v2]=distance[v]+d2;
                            Q.push(ii(v2,distance[v2]));
                        }
                    }
                }
            }
        }
    
        void printDistance()
        {
            for(int i=1;i<=V;++i)
                cout<<distance[i]<<" ";
        }
    };
    
    int main()
    {
        Graph G(5);
    
        G.addEdge(1,2,1);
        G.addEdge(1,3,2);G.addEdge(2,3,2);G.addEdge(2,4,1);G.addEdge(1,4,5);G.addEdge(4,5,1);
    
        G.dijkstra(1);
    
        G.printDistance();
    
        return 0;
    }
2

The problem is with the declaration “vector< vector > edge;”

when executing “edge[u].push_back(pair<int,int>(v,w));”, edge[u] will encounter a problem since the vector edge is initally empty.

Instead, you could use “vector< ii > edge[100005];” while declaring

Hope this helps :slight_smile:

1 Like
3

Yes, I used the “edge.resize()” option for the same and it worked. What I don’t understand is that the resizing is supposed to happen automatically right? Double the size when capacity is reached?

4

Resizing happens only when you insert(push_back) or remove(pop_back) an element (or you could use resize()). But edge[u] is just indexing(to access that element, that element must already be present). This is allowed only if the vector already has atleast u+1 elements.

More details at http://www.cplusplus.com/reference/vector/vector/