段错误：Dijkstra 的实现

Question

有人可以帮我确定为什么会出现分段错误吗？我认为这与我在 main 中为 2D 和 1D 向量分配内存的方式有关，但我不确定我做错了什么。可能是我没有考虑的调整大小函数的某些行为？

#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;
}

Answer 1

在这段代码中：

 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;
    }
  }

您在调整大小 G[j] 之前分配给 G[j][i]，因此元素尚不存在。

正如我试图建议的那样，@some-programmer-dude 更准确地建议，你应该：

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

我认为 , 0 是必需的，他不需要，他可能是对的 :o)

就样式问题而言，我建议将 V 传递给 Dijkstra 函数，或者将

const int V = G.size();

在顶部，并使用它而不是到处引用 G.size()。

段错误：Dijkstra 的实现

Segfault: Dijkstra's implementation

c++

dijkstra

segmentation-fault