87 lines
12 KiB
Markdown
87 lines
12 KiB
Markdown
# Базовые алгоритмы нахождения кратчайших путей во взвешенных графах.
|
||
[Статья с хабра](https://habrahabr.ru/post/119158/)
|
||
## Алгоритм Флойда-Уоршелла
|
||
Находит расстояние от каждой вершины до каждой за количество операций порядка **n^3**. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
|
||
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
|
||
n итераций по n итераций по n итераций, итого порядка n^3 операций.
|
||
Псевдокод:
|
||
```
|
||
прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
|
||
d = g
|
||
for i = 1 ... n + 1
|
||
for j = 0 ... n - 1
|
||
for k = 0 ... n - 1
|
||
if d[j][k] > d[j][i - 1] + d[i - 1][k]
|
||
d[j][k] = d[j][i - 1] + d[i - 1][k]
|
||
вывести d
|
||
```
|
||
## Алгоритм Форда-Беллмана
|
||
Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка **n * m**. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
|
||
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
|
||
n итераций по m итераций, итого порядка n * m операций.
|
||
Псевдокод:
|
||
```
|
||
прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)
|
||
for i = 0 ... n - 1
|
||
d[i] = 2000000000
|
||
d[0] = 0
|
||
for i = 1 ... n
|
||
for j = 0 ... m - 1
|
||
if d[e[j].second] > d[e[j].first] + e[j].value
|
||
d[e[j].second] = d[e[j].first] + e[j].value
|
||
if d[e[j].first] > d[e[j].second] + e[j].value
|
||
d[e[j].first] = d[e[j].second] + e[j].value
|
||
вывести d
|
||
```
|
||
## Алгоритм Дейкстры
|
||
Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка **n^2**. Все веса неотрицательны.
|
||
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
|
||
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
|
||
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
|
||
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
|
||
Псевдокод:
|
||
```
|
||
прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
|
||
d = g
|
||
d[0] = 0
|
||
mark[0] = True
|
||
for i = 1 ... n - 1
|
||
mark[i] = False
|
||
for i = 1 ... n - 1
|
||
v = -1
|
||
for i = 0 ... n - 1
|
||
if (not mark[i]) and ((v == -1) or (d[v] > d[i]))
|
||
v = i
|
||
mark[v] = True
|
||
for i = 0 ... n - 1
|
||
if d[i] > d[v] + g[v][i]
|
||
d[i] = d[v] + g[v][i]
|
||
вывести d
|
||
```
|
||
## Алгоритм Дейкстры для разреженных графов
|
||
Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка **m * log(n)**. Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
|
||
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
|
||
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
|
||
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
|
||
Псевдокод:
|
||
```
|
||
прочитать g // g[0 ... n - 1] - массив списков, в i-ом списке хранятся пары: first - вершина, соединённая с i-ой вершиной ребром, second - вес этого ребра
|
||
d[0] = 0
|
||
for i = 0 ... n - 1
|
||
d[i] = 2000000000
|
||
for i in g[0] // python style
|
||
d[i.first] = i.second
|
||
q.add(pair(i.second, i.first))
|
||
for i = 1 ... n - 1
|
||
v = -1
|
||
while (v = -1) or (d[v] != val)
|
||
v = q.top.second
|
||
val = q.top.first
|
||
q.removeTop
|
||
mark[v] = true
|
||
for i in g[v]
|
||
if d[i.first] > d[v] + i.second
|
||
d[i.first] = d[v] + i.second
|
||
q.add(pair(d[i.first], i.first))
|
||
вывести d
|
||
``` |