Помогите ускорить время работы алгоритма Прима

Question

Помогите ускорить время работы алгоритма Прима

Рейтинг: 1Ответов: 1Опубликовано: 30.04.2015

В задаче используется функция с алгоритмом Прима для построения остовного дерева графа, однако, мне подсказывают, что в самом алгоритме приоритет выбора следующей вершины нужно делать за O(log n), а у меня выполняется за O(n).

Как переделать мой алгоритм так, чтобы искать следующую вершину за O(log n)?

PS: Говорят делать с помощью приоритетной очереди, однако, я не пойму где ее тут использовать.

Код:

using namespace std;
const long long inf = 1001;

void My_Prima(vector<vector<pair<int, int>>> const &Vec, const int &n const&m) {
    vector <int> dista(n, inf);
    vector <bool> used(n, 0);
    dista[0] = 0;
    while (true) {
        int h = -1;
        int des = inf;
        for (int i = 0; i < n; i++) {
             if (!used[i] && (des >= dista[i])) {
                 h = i;
                 des = dista[i];
             }
        }
        if (h == -1) {
           break;
        }
        used[h] = true;
        for (int i = 0; i < Vec[h].size(); i++) {
            if (!used[Vec[h][i].first]) {
                dista[Vec[h][i].first] = min(dista[Vec[h][i].first], Vec[h][i].second);
            }
        }
    }

    long long finsuma = 0;
    for (int i = 0; i < n; i++) {
        finsuma += dista[i];
    }
    cout << finsuma;
}

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 1

Сейчас вы используете массив dista для поиска очередной вершины. Его-то вы и должны заменить на приоритетную очередь (точнее, дополнить очередью - поскольку расстояния все равно понадобятся).

Вместо первого цикла элемент извлекается из очереди. Во втором цикле вместо обновления расстояния элемент кладется в очередь - или передвигается в этой очереди, если уже там был.

Тут есть две тонкости. Во-первых, поскольку расстояние до вершины может меняться, положение вершины в очереди надо как-то обновлять. Это требует механизма слежения за положением вершины в очереди - которого нет в стандартной библиотеке. Поэтому вместо приоритетной очереди зачастую используют дерево (set), где найти вершину довольно просто.

Для передвижения вершины в такой очереди на новое место следует сначала удалить ее, потом обновить расстояние - и наконец снова добавить.

Во-вторых, вершины в очереди надо упорядочивать по расстоянию, для чего нужен специальный компаратор. Но можно поступить проще - хранить в очереди пару чисел, где первое число будет расстоянием, а второе - номером вершины.

PS

Совет по оформлению кода. Конструкции вида pair<int, int> очень плохо читаются - из них совершенно не ясно, что означает каждый из компонентов. Лучше вводить свои структуры - это занимает не сильно много строк кода, а пользы от этого куда больше.

struct edge_data {
    int end; // Номер конечной вершины ребра
    int weight; // Вес ребра

    edge_data (int end, int weight) :end(end), weight(weight) {}
}

Помогите ускорить время работы алгоритма Прима

Ответы