CODEWITHSUNDEEP
c++segmentation-faultdijkstra
Tazik_S
Tazik_S

Reputation: 163

Segfault: Dijkstra's implementation

Can someone help me determine why I'm getting a segmentation fault? I think it has to do with the way I'm allocating memory for my 2D and 1D vectors in main, but I'm not sure what I'm doing wrong. Is it perhaps some behaviour of the resize function that I'm not accounting for?

#include <queue>
#include <vector>
#include <deque>
#include <limits>
#include <iostream>
#include <algorithm>
using namespace std;

void Dijkstra(vector<vector<int>> &G, int src) {
  deque<bool> visited(G.size(), false);
  vector<int> dist(G.size(),numeric_limits<int>::max());
  queue<int> q;

  dist[src] = 0;
  q.emplace(src);
  while (!q.empty()) {
    int cur = q.front();
    for(int i = 0; i< G.size(); i++) {
      if (!visited[i] && G[cur][i]) {
        q.emplace(i);
        dist[i] = min(dist[i], G[cur][i] + dist[cur]);
      }

    }
    visited[cur] = true;
    q.pop();
  }

  for (int i = 0; i < G.size(); i++){
    if (dist[i] == numeric_limits<int>::max())
    dist[i] = -1;
    cout << dist[i] << "\n";
  }
 cout << "\n";
}



 int main() {
  int V, E, i , j, wt;
  cin >> V >> E;
  vector <vector <int> > G (V, vector <int> (V));


 for (int k = 0; k < E; ++k){ 
      cin >> i >> j >> wt;
      G[i][j] = wt;
      G[j][i] = wt; 
  }  

 Dijkstra(G, 0);
return 0;
}

Upvotes: 0

Views: 87

Answers (1)

Will Crawford
Will Crawford

Reputation: 261

In this bit of code:

 G.resize(V);
  for (i = 0; i < V; ++i){
    G[i].resize(V);
    for (j = 0; j < V; ++j){
        G[i][j] = 0;
        G[j][i] = 0;
    }
  }

you're assigning to G[j][i] before you've resized G[j], so the elements don’t exist yet.

As I tried to suggest, and @some-programmer-dude suggested more accurately, you should just have:

vector< vector<int> > G( V, vector<int> (G, 0) );

I thought the , 0 was needed, he doesn’t, he’s probably right :o)

Just as a style issue, I'd suggest passing V into the Dijkstra function, or putting

const int V = G.size();

at the top, and use it instead of referring to G.size() everywhere.

Upvotes: 1

Related Questions