Вместо введения
Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.
В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за 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;
};