Алгоритм кратчайшего пути Дейкстры некорректно работает с большими числами C ++

Question

Я пытаюсь заставить алгоритм кратчайшего пути Дейкстры работать с большими числами для взвешенного неориентированного графа с параллельными ребрами, используя очередь с приоритетом. У меня есть ограничения по памяти (64Мб) и времени (1 сек c). Проблема в том, что он дает неправильный ответ, когда граф огромен. Я знаю это, потому что существует платформа (сделанная моим университетом), на которой тестируется программа, и она показывает неправильный ответ в 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));
            }
        }
    }
}

У меня также есть это в то время как l oop в основном для заполнения графика. Количество вершин начинается с единицы, поэтому я вычитаю единицу.

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 значение 1000000000 находится на грани того, что может поместиться в 32-битное целое число со знаком - 2 ^ 31 или примерно 2 000 000 000. Если вы выполните какое-либо умножение или деление чисел с этой ошибкой, вы переполните 32-битные переменные. Даже сложение и вычитание в этом масштабе может вызвать переполнение.

Итак, вы можете:

• Уменьшить все ваши размеры совсем немного, возможно, ниже 2 ^ 15, если вы делаете большое умножение или деление.
• Используйте 64-битную математику, чтобы гарантировать сохранение точности. Для 64-разрядной версии компилятор может справиться с этим за вас, но он будет работать медленнее.
• Если вам не нужна идеальная точность для сравнений, вы можете использовать плавающую точку, так как она может охватывать гораздо большие диапазоны в стоимость точности.

И в целом: дважды проверьте с помощью sizeof(), просто чтобы быть уверенным в размерах ваших типов, а также убедитесь, что предупреждения компилятора включены, поскольку они будут ловить любое время компиляции c переливается.