时间戳

首页 > 解决方案 > 以文件为输入的最短路径

c++ - 以文件为输入的最短路径

问题描述

我正在创建一个以文件为输入的图表，并且我想计算最短路径，为此我使用了 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);
}

标签： c++algorithmgraph

解决方案

问题很可能在这里：

int d[V + 1];

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

解决方案：将其替换为std::vector. bool inQueue[V + 1]应该同样对待。

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

推荐阅读