Базовые алгоритмы нахождения кратчайших путей во взвешенных графах
Наверняка многим из гейм-девелоперов (или просто людям, увлекающимися програмировагнием) будет интересно услышать эти четыре важнейших алгоритма, решающих задачи о кратчайших путях.
Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.
Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.
Алгоритм Флойда-Уоршелла
Находит расстояние от каждой вершины до каждой за количество операций порядка 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 Алгоритм Дейкстры
Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой. Граф — структура из точек-вершин, соединенных ребрами-отрезками. Его можно представить как схему дорог или как компьютерную сеть. Ребра — это связи, по ним можно двигаться от одной вершины к другой.
Освойте профессию «Data Scientist»
Графы используют для моделирования реальных объектов, а алгоритмы поиска пути — при их изучении, а также решении практических задач. Алгоритм Дейкстры работает для графов, у которых нет ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается.
В отличие от похожих методов, алгоритм Дейкстры ищет оптимальный маршрут от одной заданной вершины ко всем остальным. Попутно он высчитывает длину пути — суммарный вес ребер, по которым проходит при этом маршруте.
Читайте также Как выбрать IT-специальность в новых реалиях?
Кто пользуется алгоритмом Дейкстры
- Математики и другие ученые, которые пользуются графами как абстрактными единицами. Задача поиска маршрута в науке может быть и чисто фундаментальной, и прикладной.
- Дата-сайентисты. В этой области много математики, в том числе активно используется теория графов.
- Сетевые инженеры, так как алгоритм Дейкстры лежит в основе работы нескольких протоколов маршрутизации. Сама по себе компьютерная сеть представляет собой граф, поэтому специалисты по сетям должны знать, что это такое.
Профессия / 24 месяца
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Зачем нужен алгоритм Дейкстры
Основная задача — поиск кратчайшего пути по схеме, где множество точек соединено между собой отрезками. В виде такой схемы можно представить многие объекты реального мира, поэтому практических примеров использования алгоритма много:
- автоматическое построение маршрута на онлайн-карте;
- поиск системой бронирования наиболее быстрых или дешевых билетов, в том числе с возможными пересадками;
- моделирование движения робота, который перемещается по местности;
- разработка поведения неигровых персонажей, создание игрового ИИ в геймдеве;
- автоматическая обработка транспортных потоков;
- маршрутизация движения данных в компьютерной сети;
- расчет движения тока по электрическим цепям.
Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей
Как работает алгоритм
Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных.
Это может звучать сложно, поэтому мы хотим показать вам, как это выглядит на примере. Возьмем такой граф: цифрами в кружках обозначены вершины, а числа возле ребер — это вес путей между ними.
Инициализация. Пусть вершиной, из которой мы будем считать маршруты, будет 0. Расстояние до самой себя у этой вершины логично равно нулю. Остальные мы пока не знаем, поэтому отметим символом бесконечности.
Расстояние от 0 до 0 помечаем равным нулю, а саму вершину — посещенной.
Первый шаг алгоритма. Мы выбираем еще не посещенную вершину с самой маленькой меткой относительно исходной — то есть такую, которая находится ближе всех. На первом шаге это одна из соседних вершин — та, которая соединена с исходной самым «маленьким» ребром.
Для графа, который мы рассматриваем, это точка 2. Мы выбираем ее, «переходим» в нее и смотрим уже на ее соседей.
Дальнейшие шаги алгоритма. Для выбранной точки нужно осмотреть соседей и записать длину пути до них с учетом пройденного пути. А потом выбрать ближнюю точку. Но есть нюанс: нужно учитывать точки, которые мы уже использовали в прошлый раз. Если они дают более «выгодный» путь, лучше воспользоваться ими.
Например, на выбранном графе есть точка 1. В нее можно перейти из точки 2, где мы находимся. Но этот путь будет длиннее, чем при переходе напрямую из точки 0, а ведь она для нас исходная. Поэтому «короткий путь» для точки 1 — это маршрут 0–1. Отмечаем вершину посещенной.
Шаги повторяются, пока на графе есть непосещенные точки. Если вершину не посетили, она не участвует в расчетах. Если после ее «открытия» появился новый, более короткий путь к какой-либо точке, то минимальное расстояние для нее перезаписывается.
Конец алгоритма. Когда непосещенные вершины заканчиваются, алгоритм прекращает работу. Результат его действия — список кратчайших маршрутов до каждой точки из исходной. Для каждого маршрута указана его длина.
Мы говорим «длина», но это условно. Например, при поиске билетов в роли веса ребра может выступать их цена, а при организации электрической цепи — расход электроэнергии.
Теория графов — обширная отрасль дискретной математики. Ее используют во множестве сфер, от химии до разработки. В профильных университетах теорию графов изучают на курсе дискретной математики. Также получить базу знаний и решать практические задачи под контролем наставника можно на курсах SkillFactory.
Data Scientist
Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.
Статьи по теме:
Кратчайшие пути
Определение. Кратчайшим путем между вершинами $a$ и $b$ в неориентированном графе называется путь между ними, содержащий наименьшее количество ребер.
В зависимости от контекста, под длиной пути может иметься в виду как число ребер ($k$), число промежуточных вершин ($k-1$), так и суммарное число вершин ($k+1$), включая начало и конец.
Кратчайший путь между парой вершин не всегда уникален.
Определение. Взвешенным графом называется граф, в котором каждому ребру сопоставляется число, называемое весом, длиной или стоимостью.
Во взвешенных графах длиной пути называется суммарная длина всех его ребер.
Если не сказано обратного, длина ребра может быть любым числом — в том числе отрицательным. В графах с отрицательными ребрами может возникнуть контринтуитивная ситуация, когда есть цикл отрицательного веса, по которому можно ходить бесконечно и таким образом получить путь произвольного малого веса между двумя вершинами, в промежутке проходя много раз по этому циклу. Поэтому обычно рассматривают графы с неотрицательными длинами ребер.
Часто требуется искать кратчайшие пути в графах. Эта задача имеет несколько тесно связанных вариаций:
- Нахождение кратчайшего пути между заданной парой вершин $a$ и $b$.
- Нахождение кратчайших путей между заданной вершиной $a$ и всеми остальными вершинами в графе.
- Нахождение кратчайших путей между каждой парой вершин в графе.
В этой главе мы рассмотрим несколько классических алгоритмов для решения этой и других смежных задач.
Как найти кратчайший путь в графе
Результатом алгоритма поиска кратчайшего пути является последовательность ребер, соединяющая заданные две вершины и имеющая наименьшую длину среди всех таких последовательностей.
На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве. К сожалению, такие действия не всегда приводят к нужному результату.
Напомним, что алгоритм построения МОД нацелен на поиск дерева с минимальным суммарным весом ребер. Рассмотрим, например, «циклический» граф, то есть такой граф, в котором первая вершина соединена со второй, вторая — с третьей, и так далее, а последняя вершина в свою очередь соединена с первой. Такой граф представляет собой просто кольцо, каждая вершина в котором соединена с двумя другими. Пример такого графа с шестью вершинами приведен на рис. 1 (а).
Обратите внимание на то, что вес каждого ребра равен 1 за исключением ребра, соединяющего вершины A и B, вес которого равен 2. Алгоритм построения минимального остовного дерева выберет все ребра веса 1, отбросив единственное ребро веса 2. Это означает, однако, что путь от A к B в минимальном остовном дереве должен проходить через все остальные вершины, а его длина равна 5 (рис. 1 (б)). Ясно, что он не является кратчайшим, поскольку в исходном графе вершины A и B соединены ребром длины 2.
Алгоритм Дейкстры
Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра. Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего пути в целом пути из начальной вершины, то мы получим требуемый результат. Точнее говоря, вот измененный алгоритм:
выбрать начальную вершину создать начальную кайму из вершин, соединенных с начальной while вершина назначения не достигнута do выбрать вершину каймы с кратчайшим расстоянием до начальной добавить эту вершину и ведущее в нее ребро к дереву изменить кайму путем добавления к ней вершин, соединенных с вновь добавленной for всякой вершины каймы do приписать к ней ребро, соединяющее ее с деревом и завершающее кратчайший путь к начальной вершине end for end while
На рис. 2 приведен пример исполнения этого алгоритма. Алгоритм выполняется на том же графе (рис. 2 (а)), что и алгоритм построения минимального остовного дерева, а искать мы будем кратчайший путь от A до G.
В начале пути из вершины A у нас есть четыре возможных ребра. Из этих четырех ребер ребро AB является кратчайшим. Поэтому мы добавляем к дереву вершину B (рис. 2 (в)) и смотрим, как следует обновить набор путей. С уже построенным деревом соединены теперь вершины E и G, поэтому их следует добавить к кайме. Кроме того, мы должны посмотреть на вершину D и сравнить прямой путь из нее в A, длина которого равна 7, с окольным путем через вершину B, длина которого равна 8. Прямой путь короче, поэтому приписанное к D ребро менять не следует. Изучив теперь имеющиеся возможности, мы видим, что кратчайшим является путь из A в C длины 4. Ребро BE короче, однако, мы рассматриваем полную длину пути из A, а такой путь, ведущий в E, имеет длину 5. Теперь к дереву кратчайших путей добавим вершину C (рис. 2 (г)). Посмотрев на граф, мы обнаруживаем, что можем пройти в вершину F через вершину C, однако длина этого пути будет равна 10 — больше, чем у прямого пути из A в F, поэтому изменения в наборе путей не производится.
На рис. 2 (г) мы можем выбрать теперь либо путь из A в F, либо путь из A в E, проходящий через вершину B: оба они имеют длину 5. Какой из путей будет выбран при исполнении программы, зависит от способа хранения данных в ней. Мы же, встретившись с необходимостью добавить вершину, будем всегда выбирать вершину, метка которой первая в лексикографическом порядке.
В результате получим ситуацию с рис. 2 (д). Добавление к дереву вершины E не меняет остальных связей, поэтому теперь мы можем добавить вершину F и получим картинку с рис. 2 (е). Обратите внимание на то, что, хотя добавление вершины F и привело к изменению ребра, ведущего из D, если бы мы начали с F, все равно на очередном шаге мы должны были бы добавить E.
На рис. 2 (е) видно, что путь в вершину D короче пути в вершину G. Поэтому мы добавляем к дереву вершину D и получаем ситуацию, изображенную на рис. 2 (ж). Осталось добавить только вершину G, и в результате мы получаем дерево кратчайшего пути с рис. 2 (з). Длина кратчайшего пути из A в G равна 10.
На примере с рис. 2 мы имеем дело с полным деревом кратчайших путей, поскольку целевая вершина G была добавлена к дереву последней. Если бы мы добрались до нее раньше, алгоритм бы тотчас завершил свою работу. Могут возникнуть ситуации, в которых нас интересуют кратчайшие пути из данной вершины во все остальные. Если, например, мы имеем дело с небольшой компьютерной сетью, скорости передачи данных между узлами которой приблизительно постоянны, то для каждого из компьютеров сети мы можем выбрать кратчайший путь до каждого из остальных компьютеров. Поэтому при необходимости переслать сообщение единственное, что нам потребуется, это воспользоваться заранее рассчитанным наиболее эффективным путем.