Блог пользователя Avitella

Автор Avitella, 11 лет назад, По-русски

Введение

Превратим обход в ширину в алгоритм Дейкстры за (n * log(n) + m * log(n))!
Данная статься предназначена в основном для участников div2, но я так же надеюсь, что и некоторым немного более продвинутым программистам будет интересно почитать. В этой статье я хотел бы описать основные алгоритмы для решения задач на графы. Однако, материала, пожалуй, не хватит, чтобы решать сложные задачи, но многие идеи, описанные здесь, вполне можно будет попробовать использовать и на сложных задачах. Материал из этой статьи можно представить, как фундамент, для изучения продвинутых алгоритмов на графах. Итак, начнем.

Обход графа в ширину

Первый алгоритм, который хотелось бы описать, и который однозначно нельзя пропустить — это обход графа в ширину. Что же это такое? Давайте немного отойдем от формального описания графов, и представим себе такую картину. Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем одно из пересечений. Как будет вести себя огонь? Он равномерно будет перекидываться по веревкам на соседние пересечения, пока не загорится все. Нетрудно обобщить эту картину и на трехмерное пространство. Именно так в жизни будет выглядеть обход графа в ширину. Теперь опишем более формально. Пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V(соседом вершины V назовем вершины, имеющий общее ребро с V). Для наглядного представления, приведу картинку.

Здесь мы начали обходить граф в ширину из вершины C. Затем мы перешли к рассмотрению вершин A, B и E.

Реализация обхода в ширину

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

void bfs(int u) {
  used[u] = true;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i];
      if (!used[v]) {
        used[v] = true;
        q.push(v);
      }
    }
  }
}

В этой реализации g — это список смежных вершин, т.е. в g[u] лежит список смежных вершин с u(в качестве списка использован std::vector), used — это массив, который позволяет понять, в каких вершинах мы уже побывали. Здесь обход в ширину не делает ничего, кроме самого обхода в ширину. Казалось бы, зачем? Однако его можно легко модифицировать для того, чтобы искать то, что нам нужно. Например расстояние и путь от какой-либо вершины до всех остальных. Следует заметить, что ребра не имеют веса, т.е. граф не взвешенный. Приведем реализацию поиска расстояний и путей.

void bfs(int u) {
  used[u] = true;
  p[u] = u;
  dist[u] = 0;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i];
      if (!used[v]) {
        used[v] = true;
        p[v] = u;
        dist[v] = dist[u] + 1;
        q.push(v);
      }
    }
  }
}

Здесь p — это массив предков, т.е. в p[v] лежит предок вершины v, dist[v] — это расстояние от вершины из которой мы начинали обход, до вершины v. Как восстановить путь? Это сделать довольно легко, просто пройдя по массиву предков нужной нам вершины. Например, рекурсивно:

void print_way(int u) {
  if (p[u] != u) {
    print_way(p[u]);
  }
  cout << u << ' ';
}

При желании, этот алгоритм можно усовершенствовать для поиска обширного списка параметров. Приводить примеры я не буду, потому что это сделать не сложно, зная принцип работы алгоритма. "Это очень легко!" — скажете вы. И все таки некоторые задачи требуют очень аккуратной реализации и нетривиальной идеи для неопытного программиста. Например, всем рекомендую решить задачу 225D - Змейка.

Кратчайшие пути

Теперь перейдем к взвешенным графам, т.е. ребра графа имеют вес. Например длина ребра. Или плата за проход по нему. Или время, которое требуется для прохода по нему. Задача — найти кратчайший путь из одной вершины, в какую-нибудь другую. В этой статье я буду отталкиваться от обхода в ширину, не помню, чтобы видел такой подход где-нибудь еще. Возможно я это пропустил. Итак, давайте посмотрим еще раз на реализацию обхода в ширину, а конкретно на условие добавления в очередь. В обходе в ширину мы добавляем в очередь только те вершины, в которых мы еще не были. Теперь же изменим это условие и будем добавлять те вершины, расстояние до которых можно уменьшить. Очевидно, что очередь опустеет тогда и только тогда, когда не останется ни одной вершины, до которой можно уменьшить расстояние. Процесс уменьшения пути из вершины V, назовем релаксацией вершины V. Следует заметить, что изначально путь до всех вершин равен бесконечности(за бесконечность возьмем какую-нибудь достаточно большую величину, а именно: такую, что ни один путь не будет иметь длины, большей величины бесконечности). Этот алгоритм напрямую следует из обхода в ширину, и именно до него я дошел сам, когда решал первую в жизни задачу на кратчайшие пути в графе. Стоит упомянуть, что такой способ ищет кратчайший пути от вершины, из которой мы начали алгоритм, до всех остальных. Приведу реализацию:

const int INF = 1e+9;

vector< pair<int, int> > g[LIM]; // В g[u] лежит список пар: (длина пути между вершиной u и v, вершина v)

void shortcut(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i].second, len = g[u][i].first;
      if (dist[v] > dist[u] + len) {
        p[v] = u;
        dist[v] = dist[u] + len;
        q.push(v);
      }
    }
  }
}

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

const int INF = 1e+9;

vector< pair<int, int> > g[LIM];
bool inque[LIM];

void shortcut(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  queue<int> q;
  q.push(u);
  inque[u] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inque[u] = false;
    for (int i = 0; i < (int) g[u].size(); i++) {
      int v = g[u][i].second, len = g[u][i].first;
      if (dist[v] > dist[u] + len) {
        p[v] = u;
        dist[v] = dist[u] + len;
        if (!inque[v]) {
          q.push(v);
          inque[v] = true;
        }
      }
    }
  }
}

Если присмотреться, то этот алгоритм очень похож на алгоритм Левита, но все-таки это не он, хотя в худшем случае работает за ту же ассимтотику. Давайте грубо оценим это. В худшем случае нам придется проводить релаксацию каждый раз, когда мы проходим по какому-либо ребру. Итого O(n * m). Оценка довольно грубая, но на начальном этапе этого вполне хватит. Стоит так же заметить, что это именно худший случай, а на практике даже такая реализация работает довольно быстро. А теперь, самое интересное! ...барабанная дробь... Улучшим наш алгоритм до алгоритма Дейксты!

Алгоритм Дейкстры

Первая оптимизация, которая приходит на ум. А давайте релаксировать те вершины, путь до которой сейчас минимальный? Собственно, именно эта идея и пришла мне в один прекрасный день в голову. Но, как оказалось, эта идея пришла первому далеко не мне. Первому она пришла замечательному ученому Дейкстре. Более того, именно он доказал, что выбирая вершину для релаксации таким образом, мы проведем релаксацию не более, чем n раз! На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем. Более формально можно прочитать на замечательном сайте e-maxx(Дружно говорим спасибо Максиму e-maxx Иванову) или на Википедии.
Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами(куча, heap). В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.

void deikstra(int u) {
  fill(dist, dist + n, INF);
  dist[u] = 0;
  p[u] = u;
  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
  q.push(make_pair(0, u));
  while (!q.empty()) {
    pair<int, int> u = q.top();
    q.pop();
    if (u.first > dist[u.second]) continue;
    for (int i = 0; i < (int) g[u.second].size(); i++) {
      int v = g[u.second][i].second, len = g[u.second][i].first;
      if (dist[v] > dist[u.second] + len) {
        p[v] = u.second;
        dist[v] = dist[u.second] + len;
        q.push(make_pair(dist[v], v));
      }
    }
  }
}

Скорее всего не совсем понятно, что здесь происходит. Начнем с объявления очереди с приоритетами. Здесь первый аргумент шаблона — данные, которые хранятся в очереди, а конкретно пары вида (расстояние до вершины, номер вершины), второй аргумент шаблона — это контейнер, в котором будут храниться данные, третий аргумент, компоратор(находится, кстати, в заголовочном файле functional). Почему нам нужен какой-то другой компоратор? Потому что при стандартном обявлении priority_queue< pair<int, int> >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Есть и другой способ, который предлагает e-maxx, будем хранить отрицательные значения длин, а при вытаскивании длины из очереди умножать на -1(подробнее прочитать можно здесь). Ассимптотика такого решения поставленной задачи O(n * log(n) + m * log(n)). Действительно, всего у нас n релаксаций, а вершину с минимальной длиной пути до нее, мы ищем за log(n)(именно такая ассимптотика у стандартной очереди с приоритетами stl). Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее. Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее. Для этого в реализации присутствует строчка if (u.first > dist[u.second]) continue;.

Заключение

Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

При наличии рёбер отрицательной длины ассимптотика портится.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Дейкстра с сетом и так просто пишется, смысл изгаляться.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Дейкстра должна была бы писаться с фибоначчиевой кучей, но неожиданно для новичков оказывается, что реализованная поверх кучи priority_queue для этого годится хуже: в ней нельзя модифицировать вершину внутри структуры, а это хочется делать при релаксации. Кстати, почему автор этого не делает?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я вас не понял. Мне не требуется модифицировать вершины внутри структуры. Как минимум вам стоило прочитать объяснения под кодом, прежде чем задавать такие вопросы.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее. Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее.

        Это написано после кода.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Конкретно мне (а я целевая аудитория, т.к. почти во втором дивизионе) непонятно, до каких размеров может раздуться priority_queue в таком случае. В случае set и самописной кучи это очевидное O(количество_вершин), а в вашем — непонятное O(общее_количество_релаксаций). Cудя по упомянутой, но недоказанной в посте информации, это O(количество_вершин^2). Надеюсь, теперь вы не видите злого умысла в простом любопытстве, почему не реализовывать буквально как в кормене у классиков.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Это всё-таки O(E) — по каждому ребру будет не более одной релаксации.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          Если в графе нету ребер отрицательной длины, то этот алгоритм работает строго за O(n + m logm). В очереди в этом случае будет находится не больше чем m вершин, потому что релаксация в этом случае возможна только один раз для каждой вершины.

          Для графов с ребрами отрицательной длины этот алгоритм лучше не применять, потому что он не является строго полиномиальным. Он конечно работает для случайных графов (наверное :) ), но лучше писать или Флойда или Беллмана-Форда.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А почему фибоначчиева куча? Всегда писал с обычной, чем лучше ваш вариант? (Я просто фибоначчиевы кучи не знаю, думал как-раз подучить, а тут еще и конкретный способ применения нарисовался)

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Всегда писал с обычной, чем лучше ваш вариант?

        На практике мало чем, потому и фибоначчиева, а не фибоначчиева. У фибоначчиевой кучи время "поднятия" вершины вверх по куче O(1), из-за чего в случае полного графа алгоритм не уступает по асимптотике (но не скрытой за ней константе) простой квадратной реализации как двоичная куча, но в таком случае на контестах нет причин не писать простую квадратную реализацию, имхо.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Только с priority_queue работает сильно быстрее (чуть ли не в два раза). Были задачи, где set валился по TL.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Ой, сомневаюсь я в умении такой штуки искать циклы отрицательной длины...

Граф:

1 3  90000
1 2 100000
2 3 -20000
3 5  9000
3 4 10000
4 5 -2000
5 7  900
5 6 1000
6 7 -200
7 9  900
7 8 1000
8 9 -200
9 11  90
9 10 100
10 11 -20
11 13  9
11 12 10
12 13 -2

Искать надо из 1 в 13. Разве там не будет 2numblocks = 26 > 13 = n релаксаций 13-й вершины? А отрицательного цикла нет...

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Давайте все-таки выясним пару вопросов. Граф ориентированный или нет? Попытаюсь рассмотреть оба ваших ответа. Ответ "нет": тут возникает некоторая проблема, по ребру отрицательного веса можно ходить туда сюда, тем самым получив сколь угодно малое расстояние до любых достижимых, так сказать, вершин от этого ребра. Скорее всего вы правы, что именно цикла по различным ребрам здесь нет, но на мой взгляд такая постановка вопроса вообще лишена смысла. Теперь рассмотрим ответ "да". Пожалуй, я задам встречный вопрос. Почему вы предъявляете претензии, даже не запустив мой код? Я ехал в раскорячку в автобусе, но, увидев ваш комментарий(через телефон), не поленился достать ноут и проверить. И что же получилось, отрицательного цикла нет. Собственно говоря в вашем примере вообще циклов нет.

    UPD. Внес исправление в статью. Этот способ верен для ориентированных графов. Для неориентированных нужно уточнять постановку вопроса.

    UPD. Удалил код с поиском цикла.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Граф ориентированный.

      Если желаете дискутировать на уровне "почему не запустил" ---выложите, пожалуйста, полный код, который можно запускать, без догадываний, какими должны быть ещё полпрограммы.

      Насколько я сумел понять, Ваш код 13-й вершине сопоставит сначала 90000+9000+900+90+9, а потом будет многократно уменьшать.

      Возможно, я и был неправ с именно этим контрпримером. Но я готов поспорить, что если не против общей идеи, то как минимум против конкретной реализации (не использующей рандомизацию) я построю контрпример аналогичной структуры, со многими такими вот треугольничками. И контрпример будет состоять в том, что цикла отрицательного веса нет, а Ваша реализация будет ошибочно утверждать, будто он есть (потому как релаксаций будет может и не именно 2(N - 1) / 2, но в любом случае очень много).

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Я буду очень рад, если вы докажете, что мой подход не верен. Внесу исправления в статью, и запомню, что так делать нельзя(**если** это действительно так). Вот код.

        UPD. Удалил код с поиском цикла.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Пример, указанный выше был немножко не для этого случая. он даёт только blockcnt релаксаций. Вот здесь релаксаций будет LBlockCnt*RBlockCnt

          12 19
          1 2 100
          2 3 -100
          3 4 10
          1 5 200 
          5 2 -202
          1 6 300 
          6 2 -303
          1 7 400 
          7 2 -404
          1 8 500 
          8 2 -505
          3 9 20 
          9 4 -22
          3 10 30 
          10 4 -33
          3 11 40 
          11 3 -44
          3 12 50 
          12 3 -55
          
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
            Rev. 9   Проголосовать: нравится 0 Проголосовать: не нравится

            Да. Я облажался :) Ну ничего, стираю кусок статьи. С остальным вроде все нормально. А вообще, я облажался еще кое в каком месте, но там тоже уже все нормально.

            UPD. А ведь ваш пример не верен. 3 11 40, а потом 11 3 -44. Вот и цикл.

            UPD. Удалил код с поиском цикла.

            UPD. Однако тест IlyaCk все равно проходит... Но идея ясна. У меня был бред. Спасибо

            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Сори. Не заметил. Не совсем комфортно вручную его забивать. Пришлось добавить еще 2 вершины, чтобы тот код, который вы выкладывали, отвечал неправильно.

              14 23
              1 2 100
              2 3 -100
              3 4 10
              1 5 200 
              5 2 -202
              1 6 300 
              6 2 -303
              1 7 400 
              7 2 -404
              1 8 500 
              8 2 -505
              3 9 20 
              9 4 -22
              3 10 30 
              10 4 -33
              3 11 40 
              11 4 -44
              3 12 50 
              12 4 -55
              1 13 600
              13 2 -606
              3 14 60
              14 4 -66
              
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Прошу обратить внимание на то, что алгоритм поиска цикла отрицательного веса был не верен. Но остальное — верно. Путь от обхода в ширину к алгоритму Дейкстры действительно прост и интересен.

»
11 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Мне вот интересно, хоть кому-нибудь оказалось полезным то, что я написал?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Ну, мне было интересно почитать. Но версия с е-макса мне нравится больше. А за статью и за старания — большое спасибо, читать интересно )

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Небольшая порция некропоста. Класс queue в плюсах очень странный, по крайней мере MS-реализация агрегируют deque. Лучше забыть о классах queue (исп. deque), stack (исп. vector) и list (по ситуации).

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Хм, и чем он странный? Чем он хуже?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Один раз я пытался пропихнуть задачу, которая получала MLE и в которой я использовал stack<T>. Потом я сообразил поменять это на stack<T, vector<T> >, и решение прокатило.

    Однако, в общем случае я всё равно придерживаюсь мнения, что надо использовать самый с точки зрения логики подходящий контейнер, если на то нет явных противопоказаний.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    И в g++ он агрегирует deque.