以文件为输入的最短路径

Question

我正在创建一个以文件作为输入的图形，我想计算最短路径，为此我使用了 SPF 算法。我有几个文件可以用来查看它是否有效，问题来了，因为它一直有效，直到我尝试使用最大的文件（它有超过 100 万个顶点和 200 万条边），考虑到第二个维度有大约 70 万个顶点和 1 亿条边，它工作得很好，你认为问题是什么？我只需要一些提示我真的想不通！请耐心等待，我是这个社区的新手，一般来说是编码，我只是想正确地学习和理解事物...... 它返回错误 3221225725

 // Function to compute the SPF algorithm
void shortestPathFaster(int S, int V)
{
    // Create array d to store shortest distance
    int d[V + 1];
 
    // Boolean array to check if vertex
    // is present in queue or not
    bool inQueue[V + 1] = { false };
 
    // Initialize the distance from source to
    // other vertex as INT_MAX(infinite)
    for (int i = 0; i <= V; i++) {
        d[i] = INT_MAX;
    }
    d[S] = 0;
 
    queue<int> q;
    q.push(S);
    inQueue[S] = true;
 
    while (!q.empty()) {
 
        // Take the front vertex from Queue
        int u = q.front();
        q.pop();
        inQueue[u] = false;
 
        // Relaxing all the adjacent edges of
        // vertex taken from the Queue
        for (int i = 0; i < graph[u].size(); i++) {
 
            int v = graph[u][i].first;
            int weight = graph[u][i].second;
 
            if (d[v] > d[u] + weight) {
                d[v] = d[u] + weight;
 
                // Check if vertex v is in Queue or not
                // if not then push it into the Queue
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
 
    // Print the result
    print_distance(d, V);
}

Answer 1

问题最有可能在这里：

int d[V + 1];

首先，可变长度数组是非标准的。其次，如果 V 很大，你会溢出堆栈。

解决方案：将其替换为std::vector。 bool inQueue[V + 1] 应该得到类似的对待。

此外，将 char buffer[BUFFER_SIZE]; 替换为 std::string。你会很高兴你做到了。

以文件为输入的最短路径

Shortest path with file as input

c++

algorithm

graph