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

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.dijkstra(1);

G.printDistance();

return 0;
}``````

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;” while declaring

Hope this helps 2 Likes

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?

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/

//