От обхода в ширину к алгоритму Дейкстры / forpes.ru

Главная
От обхода в ширину к алгоритму Дейкстры

От обхода в ширину к алгоритму Дейкстры +17

01.06.2015 17:16

Avitella 35 13181 Источник

Вместо введения

Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.

В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за priority_queue в STL C++. В конце статьи приводится краткий рассказ и ее реализация.

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

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

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

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

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 << ' ';
}

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

Все дальнейшие рассуждения будут верны только если веса ребер не отрицательны.

Теперь перейдем к взвешенным графам, т.е. ребра графа имеют вес. Например длина ребра. Или плата за проход по нему. Или время, которое требуется для прохода по нему. Задача — найти кратчайший путь из одной вершины, в какую-нибудь другую. В этой статье я буду отталкиваться от обхода в ширину, не помню, чтобы видел такой подход где-нибудь еще. Возможно я это пропустил. Итак, давайте посмотрим еще раз на реализацию обхода в ширину, а конкретно на условие добавления в очередь. В обходе в ширину мы добавляем в очередь только те вершины, в которых мы еще не были. Теперь же изменим это условие и будем добавлять те вершины, расстояние до которых можно уменьшить. Очевидно, что очередь опустеет тогда и только тогда, когда не останется ни одной вершины, до которой можно уменьшить расстояние. Процесс уменьшения пути из вершины 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 раз! На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем. Более формально можно прочитать здесь или на Википедии .

Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами (куча, heap). В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.

void dijkstra(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> >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Асимптотика такого решения поставленной задачи 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))!

Дополнение

В комментариях попросили рассказать, как можно реализовать своими руками priority_queue.

Пусть перед нами стоит следующая задача (как в алгоритме Дейкстры).
Нужно поддерживать структуру данных, которая удовлетворяет следующим требованиям:
1) Добавление не более, чем за O(log(n)) времени.
2) Удаление минимального элемента не более, чем за O(log(n)) времени.
3) Поиск минимума за O(1) времени.

Оказывается, что этим требованиям удовлетворяет структура данных, которую в русско-язычной литературе обычно называют «куча», в англо-язычной «heap» или «priority queue».

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

Теперь доопределим нашу кучу так, чтобы и остальные свойства выполнялись. Назовем уровнем вершины в дереве расстояние от корня до нее. Запретим добавлять новый уровень в куче, до тех пор пока не заполнен целиком предыдущий. Более формально: пусть текущая максимальная высота дерева H, тогда запрещено добавлять вершины на высоту H + 1, пока есть возможность добавить ее на высоту H. Действительно, при таких условиях высота кучи всегда не более, чем O(log(n)).

Осталось научиться добавлять и удалять элементы в кучу.

Реализовывать кучу будем на бинарном дереве, в котором будет не более одной вершины с количеством потомков меньшим двух. Дерево будем хранить в массиве, тогда потомки вершины на позиции pos, будут лежать на позициях 2 * pos и 2 * pos + 1, а родитель будет лежать на позиции pos / 2.

Добавлять элемент будем на первое возможное вакантное место на текущем максимальном уровне, затем выполнять операцию, которая называется «просеивание вверх». Это значит, что пока родитель добавленного элемента больше, чем сам элемент, то поменять позиции добавленного элемента и родителя, повторять рекурсивно до корня. Докажем, что при этом не нарушаются свойства кучи. Это просто, так как текущий элемент меньше, чем родитель, то он так же и меньше, чем все потомки родителя.

void push(const value_t& value) {
  data.push_back(value);
  sift_up(data.size() - 1);
}

void sift_up(size_t position) {
  size_t parent_position = position / 2;
  if (!cmp(data[position], data[parent_position])) {
    swap(data[position], data[parent_position]);
    sift_up(parent_position);
  }
}

Удалять минимальный элемент будем следующим образом: сначала поменяем местами корень дерева с последним элементом на максимальном уровне, затем удалим вершину, в которой был этот элемент (теперь там будет минимум). Свойства кучи после этого нарушатся, а чтобы их восстановить нужно выполнить операцию, которая называется «просеивание вниз». Начинаем от корня рекурсивно: для текущего элемента находим из потомков минимальный, меняем местами с текущим элементом, рекурсивно запускаемся для вершины, с которой поменяли текущий элемент. Заметим, что после этой операции, свойства кучи выполняются.

void pop() {
  swap(data[1], data.back());
  data.pop_back();
  sift_down(1);
}

void sift_down(size_t position) {
  size_t cmp_position = position;
  if (2 * position < data.size() && !cmp(data[2 * position], data[cmp_position])) {
    cmp_position = 2 * position;
  }
  if (2 * position + 1 < data.size() && !cmp(data[2 * position + 1], data[cmp_position])) {
    cmp_position = 2 * position + 1;
  }
  if (cmp_position != position) {
    swap(data[cmp_position], data[position]);
    sift_down(cmp_position);
  }
}

Так как высота дерева O(log(n)), то добавление и удаление будет работать за O(log(n)).

Весь код

template<typename value_t, typename cmp_t>
class heap_t {
 public:
  heap_t() :
      data(1) {
  }

  bool empty() const {
    return data.size() == 1;
  }

  const value_t& top() const {
    return data[1];
  }

  void push(const value_t& value) {
    data.push_back(value);
    sift_up(data.size() - 1);
  }

  void pop() {
    swap(data[1], data.back());
    data.pop_back();
    sift_down(1);
  }

 private:
  void sift_up(size_t position) {
    size_t parent_position = position / 2;
    if (!cmp(data[position], data[parent_position])) {
      swap(data[position], data[parent_position]);
      sift_up(parent_position);
    }
  }

  void sift_down(size_t position) {
    size_t cmp_position = position;
    if (2 * position < data.size() && !cmp(data[2 * position], data[cmp_position])) {
      cmp_position = 2 * position;
    }
    if (2 * position + 1 < data.size() && !cmp(data[2 * position + 1], data[cmp_position])) {
      cmp_position = 2 * position + 1;
    }
    if (cmp_position != position) {
      swap(data[cmp_position], data[position]);
      sift_down(cmp_position);
    }
  }

  cmp_t cmp;
  vector<value_t> data;
};

Комментарии (35)

eosunknown
01.06.2015 21:55
#8443149
-8
О нет, где фреймворки, где классы, код нечитаем, паттернов нет…

ivanych
01.06.2015 22:45
#8443235
+3
> Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем одно из пересечений.

Как так?
1. Avitella Автор
  02.06.2015 01:29
  #8443435
  Да, согласен. Постарался поправить формулировку

lair
01.06.2015 22:53
#8443253
+4
Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!

Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).

Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.

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

А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
1. Avitella Автор
  02.06.2015 00:40
  #8443395
  +1
  Откуда вы взяли лишнее log(n) при m? Стандартная сложность этого алгоритма при использовании кучи — O(m + n* log(n)).
  
  Если использовать фибоначчиеву кучу, то да. При использовании обычной кучи, асимптотика именно такая, как я показал.
  
  А вот и нет, интуитивно понятно, но неверно. Точнее, верно только в том случае, если вы соблюдаете ограничение применимости этого алгоритма, про которое в посте ни слова.
  
  Согласен, это верно только при не отрицательных весах ребер, сейчас допишу об этом в посте.
  1. lair
    02.06.2015 00:45
    #8443403
    А что такое «обычная куча»? Какие у нее стоимости операций?
    
    Avitella Автор
    02.06.2015 01:33
    #8443441
    Будем считать, что на верхушке кучи лежит минимум, тогда O(log(n)) на добавление, O(log(n)) на удаление минимума, O(1) на поиск минимума
1. Avitella Автор
  02.06.2015 00:44
  #8443401
  +1
  Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.
  
  Не согласен. Кучу писать совсем не сложно.
  1. lair
    02.06.2015 00:45
    #8443405
    Продемонстрируете?
    
    Avitella Автор
    02.06.2015 01:34
    #8443443
    +1
    Вы либо троллите, либо действительно не знаете. Буду исходить из второго и добавлю реализацию кучи в пост.
    
    lair
    02.06.2015 10:32
    #8443721
    Ваша реализация больше по объему, чем реализация самого алгоритма. Так, в общем-то, и должно бы быть; логика там тоже сложнее внутри (особенно когда вы все-таки добавите произвольный доступ).
    
    Mrrl
    02.06.2015 08:21
    #8443577
    Собственно, вот полная реализация:
    
    Код
    struct XVert{ int backidx; int backway; double dist; }; struct Edge{ int idx; double dist; }; struct Vert{ int NEdges; Edge *Edges; }; struct Graph{ int NV; Vert *Verts; }; double Dejkstra(Graph *G,int Start,int End){ int NV=G->NV; int LQ=NV; XVert *Verts=new XVert[NV]; Edge *Que=new Edge[NV]; for(int i=0;i<NV;i++){ int j=(i==0 || i==Start) ? Start-i : i; Verts[i].dist=100; Verts[i].backidx=j; Verts[i].backway=-1; Que[i].dist=100; Que[i].idx=j; } Verts[Start].dist=Que[0].dist=0; Verts[Start].backway=-1; for(;;){ Edge top=Que[0]; int v0=top.idx; if(top.idx==End) break; Edge btm=Que[--LQ]; int a=0,b; while((b=2*a+2)<=LQ){ if(b==LQ || Que[b].dist>Que[b-1].dist) b--; if(Que[b].dist>=btm.dist) break; Que[a]=Que[b]; Verts[Que[a].idx].backidx=a; a=b; } Que[a]=btm; Verts[btm.idx].backidx=a; Verts[top.idx].backidx=-1; for(int k=0;k<G->Verts[v0].NEdges;k++){ Edge *e=G->Verts[v0].Edges+k; double d=top.dist+e->dist; int h=Verts[e->idx].backidx; if(h<0 || d>=Verts[e->idx].dist) continue; Verts[e->idx].dist=d; Verts[e->idx].backway=v0; Edge current=Que[h]; while(h>0){ int h1=(h-1)/2; if(Que[h1].dist<d) break; Que[h]=Que[h1]; Verts[Que[h].idx].backidx=h; h=h1; } current.dist=d; Que[h]=current; Verts[e->idx].backidx=h; } } double res=Que[0].dist; delete[] Verts; delete[] Que; return res; }
    
    Mrrl
    02.06.2015 08:27
    #8443581
    Там в двух местах осталось dist=100 (со времени отладки) — заметил слишком поздно, его надо заменить на максимальное значение double.
    
    lair
    02.06.2015 10:35
    #8443727
    Пойнт не столько в размере, сколько в «концептуальной сложности». По моему опыту, написать кучу хотя бы на основе бинарного дерева сложнее, чем просто реализовать алгоритм Дийкстры — больше неочевидных мест, где можно ошибиться.
    
    (ну и будем честными, я все-таки не понял из вашего кода, как именно вы делаете замену веса, точнее — поиск элемента для замены, но это сказывается мое неумение читать terse code)
    
    Mrrl
    02.06.2015 10:54
    #8443775
    Поле XVert.backidx — текущий индекс данной вершины в массиве, на котором реализована куча (он меняется при каждом перемещении элемента кучи вверх или вниз). Поэтому, при замене веса я сразу беру индекс в массиве кучи, и начинаю двигать элемент с этим индексом вверх (если надо).
    Операции добавления вершины в кучу мне не понадобилось вообще — куча сразу создаётся со всеми вершинами, имеющими максимальный вес (кроме стартовой, у которой вес равен нулю — она кладётся в начало массива). Это приведёт к некоторой потере эффективности в ситуации, когда надо найти путь между очень близкими вершинами в очень большом графе (на первый вход в вершины потратится k*log(V) операций вместо k*log(k), где k — число вершин, которые нужно просмотреть), но код получается компактнее.
    
    lair
    02.06.2015 11:03
    #8443807
    Спасибо.
1. Mrrl
  02.06.2015 07:10
  #8443525
  +1
  Ну и да, легко это писать, когда за вас куча реализована фреймворком, а вот когда вы эту кучу делаете ручками, все не так радужно.
  
  Реализация приоритетной очереди — 25-30 строк, ненамного больше остальной части алгоритма.
  
  Откуда вы взяли лишнее log(n) при m?
  
  Заметим, что в статье ни разу не говорилось, что такое n и m. Можно догадаться, что одно из них — вершины, а другое — рёбра, но что есть что — непонятно.
  При данной реализации — когда вершины со старыми весами остаются в куче до тех пор, пока не дойдёт очередь до их старого веса — размер кучи может доходить до O(E), где E — число рёбер. Например, так будет для графа с вершинами 1..V, где d(m,n)=2*abs(m-n)-1, и мы ищем путь от 1 до n. Каждый новый улучшенный экземпляр вершины придётся положить в кучу, на это потребуется до E*log(E) операций.
  1. lair
    02.06.2015 10:37
    #8443729
    «Традиционно» n = |V|, m = |E|.

lair
02.06.2015 00:54
#8443413
Кстати, а где в вашем алгоритме замена весов ранее вставленных вершин? Иными словами, если на шаге один в кучу добавлена вершина u с весом 15, а на шаге три в кучу добавлена эта же вершина с весом 3 — сколько записей о вершине u будет в куче?
1. Avitella Автор
  02.06.2015 01:36
  #8443445
  В посте описано. Нужно не проводить релаксацию, если из кучи достали неактуальный путь.
  1. lair
    02.06.2015 10:39
    #8443735
    При такой реализации, как уже написано выше, вы получаете высоту кучи в O(log|E|), что для полного графа равно O(log(|V|²) (это в расчете на то, что дублирующиеся ребра вы оптимизируете на предварительном этапе), против O(log(|V|) в стандартной реализации.
    
    Mrrl
    02.06.2015 11:02
    #8443805
    O(log|E|), что для полного графа равно O(log(|V|^2))… против O(log(|V|)
    
    Хорошая попытка :)
    
    К счастью, O(log (|V|^2)) = O(2*log |V|) = O(log |V|), так что мы теряем не более, чем константу (а может быть, и выигрываем — ведь нам не нужно поддерживать функцию уменьшения веса).
    Память на кучу проигрываем, причём сильно — это верно. Если граф у нас не хранится в памяти, а как-то вычисляется, то это может быть плохо.
    
    lair
    02.06.2015 11:05
    #8443811
    O(log (|V|^2)) = O(2*log |V|) = O(log |V|),
    
    Если так считать, то можно ограничиться стэнфордским определением асимптотики алгоритма в O(|E| log |V|) и не мучиться разницей между разными реализациями кучи.
    
    (собственно, наивная функция уменьшения веса — 2*log(n), потому что сводится к удалению и вставке, оба из которых реализуемы на двоичной куче за log(n)),
    
    Mrrl
    02.06.2015 11:33
    #8443881
    1) Между O(2*log(|V|) и O(log(|E|*log(|V|) есть небольшая разница: 2 это константа, а log(|E|) — нет. Определение O(f(x)) даётся так, что изменение f(x) в константу раз на результат не влияет. А если f(x) умножается на величину, зависящую от x, то класс алгоритмов и их асимптотика может измениться.
    2) Операции «удаление произвольного элемента» в наивной реализации кучи не предусмотрено — она бы потребовала просмотра всей кучи. А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый: ведь добавление элемента в кучу фактически реализуется как добавление его в конец массива с бесконечным весом плюс последующее уменьшение веса.
    
    lair
    02.06.2015 11:46
    #8443911
    Между O(2*log(|V|) и O(log(|E|*log(|V|)
    
    А откуда вы взяли log(|E|*log(|V|))?
    
    А если мы умеем быстро искать элемент, то изменить его вес так же просто, как добавить новый
    
    Не совсем — нам надо не забыть восстановить инварианты по отношению к тому месту, откуда мы «вытаскиваем» элемент. Это не сложно, но тоже требует аккуратности. Собственно, здесь и накапливается сложность (не алгоритмическая) реализации кучи.
    
    Mrrl
    02.06.2015 11:52
    #8443933
    Когда мы добавляем новый элемент (или удаляем минимум), то при реализации через массив у нас меняется положение части элементов в массиве. И для них всё равно приходится отслеживать изменение информации для поиска. Если вы знаете способ реализовать кучу с удалением произвольного элемента, в котором добавление операции изменения веса (отличной от удаления+вставки) приводит к заметному усложнению реализации — было бы интересно взглянуть.
    
    lair
    02.06.2015 12:28
    #8444017
    Ну, как я это в свое время реализовывал: при вставке мы получаем bubble-up. При снятии верха — bubble-down. При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов. С моей точки зрения (ну и банально по тому, сколько времени я потратил на отлов багов) вот это «то либо другое» и есть усложнение реализации.
    
    Но я, правда, говорю про generic heap, который просто структура данных, отвязанная от алгоритма.
    
    mird
    06.06.2015 19:10
    #8451011
    При вытаскивании элемента из середины — не важно, для удаления или для перевесовки, — нужно сделать либо то, либо другое, в зависимости от отношения весов элементов.
    
    Дешевле всего вызвать и то и другое. По количеству операций получается не больше операций чем если проверять соотношение весов и вычислять направление «всплытия»
    
    Mrrl
    07.06.2015 17:38
    #8451463
    «И то и другое» — вы имеете в виду удаление и последующую вставку с новым весом? В случае бинарной кучи это безумно дорого. Обычно при уменьшении веса объект либо не надо двигать вообще (он уже тяжелее своего родителя), либо его надо переставить на 1-2 ступеньки вверх. И сравнивать на каждом этапе только с родителем. А удаление+вставка — это надо сначала утопить самый тяжелый объект, вставленный на место удалённого (2*log(K) сравнений, где K — положение нашего объекта, считая снизу), а потом — всплыть наш объект с самого последнего места (ещё не менее log(K) сравнений). Если мы уменьшаем вес объекта, близкого к вершине, то потребуется до 3*log(N) сравнений (и 2*log(N) перемещений), когда хватило бы совсем маленьких значений.
    
    mird
    08.06.2015 08:41
    #8451849
    И то и другое — это вызвать метод всплытия а потом метод утопления. Потому что когда вы удаляете объект из середины, вы меняете удаляемый объект с последним элементом, после этого элемент нужно расположить на нужном уровне. И этот уровень может быть как выше так и ниже. При этом один из вызовов в данном случае делает только проверку что перемещать объект не надо и выходит.
    
    Mrrl
    08.06.2015 09:02
    #8451863
    Согласен. Редкая ситуация, но может случиться.
    
    mird
    08.06.2015 10:39
    #8451975
    +1
    На самом деле эта ситуация не так редка как может показаться. Она может возникнуть, когда последний элемент находится в другой ветке относительно элемента который мы удаляем.
    Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
    
    lair
    08.06.2015 12:55
    #8452205
    Собственно, когда я реализовывал этот самый алгоритм Дийкстры, я при реализации «кучи» сделал только утопление, считая, что если я поменял с последним элементом, этот элемент должен потонуть обратно вниз. Потом сутки пытался понять почему у меня с вероятностью 70% получается неверный результат.
    
    +1
    
    Собственно, именно поэтому я говорю, что в реализации алгоритма Дийкстры с кучей куча — самое сложное место.

ShashkovS
02.06.2015 10:06
#8443689
+2
Я просто оставлю это здесь: e-maxx.ru/algo/dijkstra_sparse.
Вообще e-maxx.ru — замечательный сайт по алгоритмам, автор которого даже присутствует на хабре.
1. encyclopedist
  02.06.2015 13:33
  #8444227
  В статье есть ссылки на e-maxx, так что автор знает о существовании этого замечательного сайта.

От обхода в ширину к алгоритму Дейкстры +17

Вместо введения

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

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

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

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

Вместо заключения

Дополнение

Комментарии (35)

Avitella Автор

Avitella Автор

Avitella Автор

Avitella Автор

Avitella Автор

Avitella Автор