[Из песочницы] От обхода в ширину к алгоритму Дейкстры01.06.2015 21:48
Вместо введения
Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.Обход графа в ширину
Первый алгоритм, который хотелось бы описать, и который однозначно нельзя пропустить — это обход графа в ширину. Что же это такое? Давайте немного отойдем от формального описания графов, и представим себе такую картину. Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем одно из пересечений. Как будет вести себя огонь? Он равномерно будет перекидываться по веревкам на соседние пересечения, пока не загорится все. Нетрудно обобщить эту картину и на трехмерное пространство. Именно так в жизни будет выглядеть обход графа в ширину. Теперь опишем более формально. Пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V (соседом вершины V назовем вершины, имеющий общее ребро с V). И так до тех пор, пока все вершины в графе не будут просмотрены.Реализация обхода в ширину
Пусть мы находимся в какой-то вершине в процессе обхода в ширину, тогда воспользуемся очередью, в которую будем добавлять всех соседей вершины, исключая те, в которых мы уже побывали.
void bfs (int u) {
used[u] = true;
queue 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 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 > g[LIM]; // В g[u] лежит список пар: (длина пути между вершиной u и v, вершина v)
void shortcut (int u) {
fill (dist, dist + n, INF);
dist[u] = 0;
p[u] = u;
queue 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 > g[LIM];
bool inque[LIM];
void shortcut (int u) {
fill (dist, dist + n, INF);
dist[u] = 0;
p[u] = u;
queue 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 deikstra (int u) {
fill (dist, dist + n, INF);
dist[u] = 0;
p[u] = u;
priority_queue< pair, vector< pair >, greater< pair > > q;
q.push (make_pair (0, u));
while (! q.empty ()) {
pair 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 >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Асимптотика такого решения поставленной задачи 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))!
© Habrahabr.ru
