Dijkstra最短路径算法不适用于大量C ++

Question

我正在尝试使用优先级队列使Dijkstra最短路径算法适用于具有平行边的加权无向图的大量运算。我有内存（64Mb）和时间（1秒）限制。问题是当图形很大时，它给出了错误的答案。我知道这是因为有一个平台（由我的大学制造）正在测试程序，并且在第13个测试中显示错误的答案占用了比以前的测试更多的内存。

typedef unsigned long int vertex_t;
typedef unsigned long int weight_t;

const weight_t max_weight = 1000000000;

struct neighbor 
{
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }
};

typedef pair<weight_t, vertex_t> weight_vertex_pair_t;

void ShortestPath(vertex_t source, vertex_t target, 
                    const vector<vector<neighbor> > &adjacency,
                    vector<weight_t> &min_distance, vector<vertex_t> &previous)
{
    int n = adjacency.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    priority_queue<weight_vertex_pair_t, vector<weight_vertex_pair_t>,
            greater<weight_vertex_pair_t> > vertex_queue;
    vertex_queue.push(make_pair(min_distance[source], source));

    while (!vertex_queue.empty()) 
    {
        weight_t dist = vertex_queue.top().first;
        vertex_t u = vertex_queue.top().second;
        if (u == target)
        {
            cout << min_distance[u];
            break;
        }
        vertex_queue.pop();

        if (dist > min_distance[u])
            continue;

        const vector<neighbor> &neighbors = adjacency[u];
        for (vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
             neighbor_iter != neighbors.end();
             neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t u_distance = dist + weight;
            if (u_distance < min_distance[v]) 
            {
                min_distance[v] = u_distance;
                previous[v] = u;
                vertex_queue.push(make_pair(min_distance[v], v));
            }
        }
    }
}

我在主循环中也有这个while循环来填充图形。顶点数从1开始，这就是为什么我要减去1。

while (y < edges)
{
     cin >> a >> b >> c; // vertex, neighbor, weight
     adjacency[a-1].push_back(neighbor(b-1, c));
     adjacency[b-1].push_back(neighbor(a-1, c));
     y += 1;
}

Answer 1

让我们回答这个问题，因为它似乎已经达成共识：

您的max_weight值1,000,000,000就在可以容纳32位有符号整数-2 ^ 31或大约2,000,000,000的边缘。如果您对该数字进行任何形式的乘法或除法运算，则将溢出32位变量。即使以该比例进行加减也会导致溢出。

因此，您可以：

• 将所有大小缩小很多，如果进行大的乘法或除法，可能会小于2 ^ 15。
• 使用64位数学运算可确保保留您的精度。对于64位，编译器可能会为您处理，但运行速度会较慢。
• 如果不需要比较精确的精度，则可以使用浮点，因为浮点可以跨越更大的范围，但以精度为代价。

并且通常：用sizeof()仔细检查，以确保您的类型大小，并确保启用了编译器警告，因为它们将捕获任何静态编译时间溢出。