0

Моя реализация класса "граф", метод PathWeights реализует алгоритм Дейкстры для ориентированного взвешенного графа:

const int HUGE_NUMBER = 100000000; //

typedef std::pair<int, uint64_t> Arrow;

bool ArrowCmp(const Arrow &lhs, const Arrow &rhs) {
  return lhs.first < rhs.first;
}

class Graph {
  int size_;

  std::vector<std::vector<Arrow>> arrows;
  std::vector<int> parents;

 public:
  explicit Graph(int size) {
    size_ = size;
    arrows.resize(size);
    parents.resize(size);
  }

  void AddEdge(int from, int to, uint64_t cost) {
    if (from == to) {
      return;
    }

    auto arrow = std::make_pair(to, cost);

    auto pos = std::lower_bound(arrows[from].begin(),
                                arrows[from].end(),
                                arrow,
                                ArrowCmp);

    if (pos == arrows[from].end()) {
      arrows[from].push_back(arrow);
    } else if (pos->first != arrow.first) {
      arrows[from].insert(pos, arrow);
    } else {
      (*pos).second = std::min(cost, pos->second);
    }
  }

  std::vector<int> Path(int from, int to) {
    PathWeights(from);

    std::vector<int> ret;

    for (int cv = to; cv != from; cv = parents[cv]) {
      ret.push_back(cv);
    }

    ret.push_back(from);
    std::reverse(ret.begin(), ret.end());

    return ret;
  }

  std::vector<uint64_t> PathWeights(int start) {
    std::vector<uint64_t> lens(size_);

    std::fill(lens.begin(), lens.end(), HUGE_NUMBER);
    lens[start] = 0;

    int count = 0;

    std::set<std::pair<uint64_t, int>> sorted_ps;

    sorted_ps.insert(std::make_pair(0, start));

    while (!sorted_ps.empty()) {
      int from = sorted_ps.begin()->second;
      sorted_ps.erase(sorted_ps.begin());

      for (int to = 0; to < size_; ++to) {
        auto arrow = std::make_pair(to, 0ul);
        auto pos = std::lower_bound(arrows[from].begin(),
                                    arrows[from].end(),
                                    arrow,
                                    ArrowCmp);

        if (pos == arrows[from].end()) {
          continue;
        }

        if (pos->first != to) {
          continue;
        }

        auto cost = pos->second;

        if (lens[from] + cost < lens[to]) {
          sorted_ps.erase(std::make_pair(lens[to], to));
          lens[to] = lens[from] + cost;
          parents[from] = to;
          sorted_ps.insert(std::make_pair(lens[to], to));
        }
      }
      ++count;
    }

    return lens;
  }
};

Я пытаюсь решить задачу из закрытого контеста, условие задачи можно сформулировать так:

  1. Дан ориентированный взвешанный граф, в котором могут быть петли и кратные ребра
  2. Веса - целые числа от нуля до двух
  3. Вершин меньше 5000, ребер меньше 20000
  4. Нужно найти вес самого легкого пути между двумя данными вершинами
  5. В main не больше 10000 вызовов PathWeights
  6. Программа должна использовать не больше 64Mb памяти, работать не дольше 3 секунд

Сейчас программа работает верно, но медленно.

Первое решение хранило ребра в виде матрицы смежности, а подходящую вершину искало линейным поиском, использую булевый массив. Сейчас я использую вектор исходящих ребер, отсортированныц по возрастанию индекса конечной вершины, и set для выбора подходящей вершины. Можно ли как-то еще ускорить это решение? Стоит ли при этих условиях использовать другой алгоримт?

4
  • Не пробовали написать алгоритм Флойда? Кажется, что его можно запихнуть в три секунды на таких ограничениях.
    – EzikBro
    12 фев 2022 в 11:56
  • Вершин меньше 5000, ребер меньше 20000 - значит, графы с большим количество вершин разреженные, для таких есть специальные методы с лучшей асимптотикой
    – MBo
    12 фев 2022 в 16:35
  • Не подскажете, в какую сторону гуглить? Я пока ничего не смог найти
    – Rennorb
    13 фев 2022 в 14:01
  • Вот, например. Правда, с петлями и кратными рёбрам я дела не имел, но для решёточного графа 2.5 миллиона узлов за 1.3 с обрабатывалось (пример на Delphi)
    – MBo
    13 фев 2022 в 15:05

2 ответа 2

2

С вот этим местом явно что-то не так:

   for (int to = 0; to < size_; ++to) {
     auto arrow = std::make_pair(to, 0ul);
     auto pos = std::lower_bound(arrows[from].begin(),
                                 arrows[from].end(),
                                 arrow,
                                 ArrowCmp);

Имеем линейный проход по всем вершинам графа, плюс ещё бинпоиск, а тут достаточно было проитерироваться по всем парам в arrows[from]. Это явно основная проблема этого кода в плане временной сложности.

Ещё заметил строчку parents[from] = to; - точно не наоборот?

Также советую побенчмаркать AddEdge. У меня смутное подозрение, что все эти манипуляции со вставкой в середину вектора могут нехило ухудшить производительность. Мне вообще никогда не приходилось в списках рёбер поддерживать инвариант "исходящие рёбра отсортированы". Возможно, лучше от него избавиться? Зачем он здесь?

3
  • В AddEdge, по идее, все эти фокусы нужны для того, чтобы хранить только самое короткое из кратных ребер, но я проверил, если все заменить на push_back, лучше не становится
    – Rennorb
    12 фев 2022 в 15:14
  • Да, вы правы, цикл остался от матрицы смежности, если его убрать, становится сильно быстрее: тот тест, который раньше занимал 3.077s, теперь отрабатывает за 181ms
    – Rennorb
    12 фев 2022 в 15:17
  • Обидно, что даже с таким ускорением программа все равно работает дольше трех секунд на поздних тестах
    – Rennorb
    12 фев 2022 в 15:33
0

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

  1. Расстояние L до той вершины, которая сейчас обрабатывается, больше или равно всем предыдущим расстояниям
  2. Новое минимальное расстояние находится во множестве {L, L+1, L+1}.

Это позволяет отказаться от сета и использовать три вектора, каждый для своего расстояния, а новую вершину получать c помощью .end(); .pop_back(), кажется, что это упрощает O(V+E log E) до O(V+E).

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.