Базовые алгоритмы нахождения кратчайших путей во взвешенных графах

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе 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
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 30
  • +2
    А как же A*, в котором есть эвристика? Интересно бы было почитать про возможности нахождения пути с использованием GPU.
    • –1
      Когда я писал эту статью, я забыл упомянуть в заголовке, что я рассматриваю только взвешенные графы.
      • 0
        Разве волновой алгоритм не подходит для любого графа?
        • 0
          Волново́й алгори́тм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины.
          • +2
            Не вижу проблем его использовать для ребер разного веса.
            • 0
              в случае взвешенного графа асимптотика что поиска в глубину, что поиска в ширину начинает сильно отличаться от O(e + v) в худшую сторону, грубо говоря мы в каждую вершину вместо одного раза сможем попасть ~v^2 раз каждый раз релаксируя результат и пуская новую волну, что и говорит о его неприменимости для поиска кратчайших путей
              • 0
                Вроде, зависит от реализации?
                • 0
                  зависит от теста, и в вашем примере граф невзвешенный, очевидно

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

              Практическое применение

              Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.
              И да, как правильно заметили, то, что он ориентирован на ребра единичной длинны не мешает модифицировать его для прочих нужд.
          • 0
            В одном своём проекте я использую А* именно в взвешенном графе. Веса неотрицательные. Просто А* не считается базовым с точки зрения математики, потому что там самое важное — эвристическая функция оценки расстояния.
        • 0
          Почему бы для вашего псевдокода не использовать тег source?
          <source lang="java">
              <!-- Code here -->
          </source>
          
          • –3
            Спасибо за ваш совет, учту на будущее. К сожалению сейчас править слишком много.
            • +5
              Сделать читабельнее четыре блока кода ради того, чтобы многократно повысить качество статьи?
              Простите, но сейчас, имхо, код выглядит как каша — без подсветки, с навязчивыми линиями слева и пропорциональным шрифтом.
              • +1
                Поправил, стало заметно лучше.
        • +2
          Я почему-то всегда считал самыми базовыми волновой алгоритм и А*

          • 0
            К сожалению, А* показывает не очень хорошую скорость. И, например, в стратегии, где надо пускать много юнитов по длинному пути (выбрали пачку из 100 юнитов и шлём на вражескую базу за речкой в другом конце карты) в обычном виде будет страшно глючить.

            Я бы с удовольствием почитал об оптимизациях этих алгоритмов. Были мысли о кешировании результата (но как корректно применить кеш, что делать при динамически меняющейся карте) и (бить карту на блоки/использовать контрольные точки). Но всё-же хотелось бы почитать про готовые решения.
              • 0
                Интересно, а какой алгоритм на какой основе показывает лучший результат? А* с хорошей эвристикой, по-моему, лучший алгоритм для нахождения пути на клетчатом поле.
                • +1
                  Имхо, тоже, но без оптимизации он слишком медлителен.
                  Был пример на Флеше. При более менее загруженной карте (а она всего лишь 60*60) — поиск пути для одного юнита — 200 мс:


                  Тут есть ещё одна дилемма для оптимизации — считать ли первый найденный маршрут самым коротким, или поискать более короткий?
                  • 0
                    Если соблюдено некое условие для эвристической функции, то алгоритм всегда находит минимальный путь (или один из минимальных). Условие звучит примерно так, что оценка не должна превышать минимально допустимый теоретический путь. Могу ошибаться.
                    • 0
                      Ну можно искать любой путь, а не самый короткий. Возможно, это будет быстрее, плюс велика вероятность таки нахождения самого короткого пути, но не факт.
                • 0
                  К сожалению, А* показывает не очень хорошую скорость.
                  Базовый — не значит оптимальный или лучший. Хотя А* достаточно сбалансирован для большинства задач. Базовый — это основной или простейший, на котором легко показать основные задачи алгоритма в целом. ИМХО конечно.
                • 0
                  Насколько я помню, этот алгоритм оптимизирует решения нескольких функций в многомерном пространстве (обычно больше 2). Он слишком далёк от реального поиска пути.
                  • 0
                    А если сделать одну функцию минимума и одну функцию оценки, и искать кратчайший путь по этим двум функциям? Транспортные задачи симплекс-метод решает на ура, самое длинное решение, которое я видел — 20 итераций. Хотя да, возможно, что составление матрицы потребует больше итераций, чем любой из приведенных алгоритмов.
                • +2
                  Действительно, в этой статье алгоритмы поиска в графе описаны в больше мере с математической точки зрения, нежели с точки зрения гейм-дева.

                  В играх поиск пути обычно заканчивается на А* и компании ( IDA, D*, fringe search ) а дальше идут специфичные для представления и топологии карты оптимизации — иерархический поиск, мемоизация, прогрессивное улучшение, адаптивный поиск итп. Если же игра — интерактивная, то найденное решение требует дальнейшей обработки с учетом динамических коллизий, сглаживания и всего остального.

                  Кстате, стоит упомянуть, что поиск на графе даже в гейм-деве не ограничивается картами. Это так же ИИ, планирование и многое другое.
                  • 0
                    Кратчайшие пути не только в играх нужны. В связи есть целое направление по проектированию сетей связи с целью получить наиболее оптимальный вариант сети с заданной надёжностью.
                    • 0
                      Разумеется, но в данном случае автор в самом начале статьи сослался на гейм-дев.
                      • 0
                        Действительно, просмотрел. Просто у меня был конспект лекций СибГУТИ в электронном виде (набирал когда учился в odt), где вопросы построения сетей связи рассматриваются на уровне графов. Если интересует, могу поискать.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.