Кратчайший путь в графе а3: A3 — Кратчайший путь в графе

А3 кратчайший путь в графе ответы

Рассмотрим решение задачи 3 ГИА 2013 по информатике

Между населёнными пунктами A, B, C, D, E, F построены дороги,
протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и F. Передвигаться
можно только по дорогам, указанным в таблице.

1) 9 2) 11 3) 13 4) 15

Решение

Для удобства отобразим табличные данные в виде графа

Решение задачи 2 ГИА по информатике

Теперь переберем все возможные пути из A в F:

Как видно, кратчайший вариант A-C-D-F = 13км. Правильный ответ 3.

Чтобы не запутаться, рекомендуется перебирать пункты в алфавитном порядке.

Дополнение (ГИА 2014)

Для более качественной подготовки к ГИА по информатике рассмотрим решение задачи 3 ГИА 2014 по информатике (демоверсия ФИПИ 2014)

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

1) 4 2) 5 3) 6 4) 7

Решение:

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

Задача 3 ГИА 2014 по информатике

Осталось рассмотреть все возможные маршруты из A в E и найти кратчайший из них. При этом обращаем внимание на то, что в пункт E мы можем попасть только из пункта C.

Как видим, минимальное расстояние — 5 километров (маршрут A-B-C-E). Правильный ответ 2.

Рассмотрим решение задачи из диагностической работы ГИА по информатике 19 декабря 2013 года

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

ИНФ90301 задача 3

Определите длину кратчайшего пути между пунктами A и B (при условии, что передвигаться можно только по построенным дорогам).

1) 11 2) 12 3) 13 4) 14

Решение:

Преобразуем таблицу в граф для удобства.

граф к задаче 3

Осталось перебрать все маршруты из A в B и посмотреть их длину:

A-D-C-E-B = 10+1+3+1 = 15

Как видим, минимальный по длине маршрут A-C-E-B, который составляет 12 километров. Правильный ответ 2.

Автор: Александр Чернышов

Оцените статью, это очень поможет развитию сайта.

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и E. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

Найдём все ва­ри­ан­ты марш­ру­тов из A в E и вы­бе­рем самый короткий.

Из пунк­та A можно по­пасть в пунк­ты B, С.

Из пунк­та B можно по­пасть в пунк­ты C, D.

Из пунк­та C можно по­пасть в пункт D.

Из пунк­та D можно по­пасть в пункт E.

A—B—C—D—E: длина марш­ру­та 13 км.

A—B—D—E: длина марш­ру­та 10 км.

A—C—D—E: длина марш­ру­та 10 км.

A—C—B—D—E: длина марш­ру­та 9 км.

Самый ко­рот­кий путь: A—C—B—D—E. Длина марш­ру­та 9 км.

• Попроси больше объяснений
• Следить
• Отметить нарушение

14.01.2015

Что ты хочешь узнать?

Ответ

Проверено экспертом

Данную задачу можно представить в виде графа для более наглядного решения (см. рисунок 2)
Здесь черные кружки — это пункты
Красные линии — это возможные пути перехода из одного пункта в другой
Если от одного пункта к другому нет линии, значит нельзя перейти о чем в таблице свидетельствует пустая клетка на перекрестье пунктов в таблице.
на рисунке 1 показано как найти расстояние от B до С или от С до B (направление не имеет разницы)

Для задачи с маленьким количеством пунктов (как в примере) можно воспользоваться простым перебором
следуя от пункта А к пункту Е, складывая длины переходов, тем самым можно найти наименьший.

Например (путь A-B-C-E)
2+1+2=5
путь A-D-C-E
1+3+2=5
пусть A-C-E
5+2=7
Отсюда мы видим что минимальный путь равен 5

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе / Хабр

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.

Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина — источник. Остальным вершинам присвоим метки равные бесконечности.

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

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р — Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W — P[4]=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

Задание №3. Таблицы и схемы

Автор — Лада Борисовна Есакова.

В своей деятельности человек повсеместно использует модели, то есть создает образ, упрощенную копию того объекта, с которым ему приходится иметь дело.

Модель — это искусственно созданный объект, дающий упрощенное представление о реальном объекте, процессе или явлении, отражающий существенные стороны изучаемого объекта с точки зрения цели моделирования.

Моделирование — это построение моделей, предназначенных для изучения и объектов, процессов или явлений.

Распространенными информационными моделями являются графики, схемы, таблицы, диаграммы. Одним из распространенных видов моделей являются графы. Граф – это один из способов графического едставления информации. Объекты представлены в нем как вершины (узлы), а связи между объектами как ребра (дуги). Т.е. граф – это набор вершин и связывающих их ребер.

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

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

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

Дерево – это граф, не имеющий циклов. В дереве существует один единственный путь между любой парой вершин. Одна из вершин дерева (корень) не имеет входящих ребер, все остальные имеют ровно одно входящее ребро. Вершины, у которых нет исходящих ребер, называются листьями.

1. Поиск графа, соответствующего таблице

Пример 1.

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

Решение:

Сравним значения таблицы и схем:

Согласно таблице вершина A должна быть связана с вершинами B (значение 4) и D (значение 5). Т.е. AB=4, AD=5. На схеме значения указаны около соответствующего ребра. Сразу отбрасываем 1),2),3) схемы, т.к. на них AD не равно 5.

Для уверенности проверим все остальные ребра схемы 4): BC=3, BD=6, что совпадает со значениями таблицы. Правильная схема 4).

Ответ: 4

2. Анализ информации в таблице и графе

Пример 2.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Решение:

На графе из вершины В выходит 5 ребер, значит в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6.

На графе из вершины Е выходит 4 ребра, значит в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4.

Таким образом, нам нужно найти расстояние между П6 и П4. Согласно таблице оно равно 20.

Ответ: 20

3. Поиск информации в таблице по условию

Пример 3.

Между четырьмя местными аэропортами: ЛУГОВОЕ, ДЯТЛОВО, НИКИТИНО и ОРЕХОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Путешественник оказался в аэропорту ЛУГОВОЕ в полночь. Определите самое раннее время, когда он может попасть в аэропорт ОРЕХОВО. Считается, что путешественник успевает совершить пересадку в аэропорту, если между временем прилета в этот аэропорт и временем вылета проходит не менее часа.

1) 12:05 2) 12:50 3)12:55 4) 13:30

Решение:

Можно, конечно, решить эту задачу просто глядя на таблицу и перебирая подходящие варианты, но есть риск ошибиться или пропустить нужную строчку. Поэтому рекомендую нарисовать дерево всех возможных путей из аэропорта ЛУГОВОЕ в ОРЕХОВО:

Средняя ветка не подходит, т.к. между прилетом в аэропорт ДЯТЛОВО (11:15) и вылетом из ДЯТЛОВО в ОРЕХОВО (12:00) интервал меньше часа.

Из оставшихся двух выбираем раннее время прилета: 12:55.

Ответ: 3

4. Выбор таблицы по условию

Пример 4.

В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

Решение:

По каждой из схем построим дерево с корнем в точке C и листьями в точке B. При этом нам не нужно строить дерево полностью. Как только найдена ветка с протяженностью больше 6, делаем вывод, что таблица не удовлетворяет указанному условию:

Таблицы 1), 2) и 4) отвергаем уже при анализе первой ветки дерева.

В таблице 3) две ветки вообще не приведут в B, а две другие имеют суммарную длину, не превышающую 6.

Ответ: 3

5. Поиск кратчайшего пути по таблице

Пример 5.

Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

1) 13 2) 16 3) 19 4) 21

Решение:

При решении этой задачи тоже не следует полагаться на простой визуальный анализ таблицы. Чтобы избежать ошибок, построим дерево с корнем в вершине A и листьями в вершине Z. При этом нам не нужно выписывать все ветки. Второй путь из A в С (AC=6) длиннее первого (ABC=5), значит и весь маршрут через него будет длиннее.

Второй путь из C в E (CE=10) длиннее первого (CDE=6), значит и весь маршрут через него будет длиннее.

Нам остается сложить длины всех отрезков и выбрать маршрут с наименьшей длиной.

Это верхняя ветка дерева с длиной 16.

Ответ: 2

Задание №15. Графы. Поиск количества путей

Автор — Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

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

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

🌌 10 анимированных алгоритмов на графах

Графы стали мощным средством моделирования и представления данных из задач реального мира, таких, как социальные сети, веб-страницы и ссылки, а также локации и маршруты в GPS. Если есть набор связанных друг с другом объектов, их можно представить в виде графа.

В этой статье мы вкратце опишем десять широко применяемых алгоритмов на графах и их приложения. Для начала давайте освежим свои знания о графах.

Что такое граф?

Рис. 1. Визуализация терминологии графов

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

• Путь – последовательность вершин, в которой каждая вершина соединена со следующей вершиной ребром. На Рис. 1 красными стрелками показан путь от вершины 1 к верешине 3 через вершину 4.
• Порядок – количество вершин графа.
• Размер – количество ребер графа.
• Связность (степень связности) вершины – количество ребер, исходящих из этой вершины.
• Изолированная вершина – вершина, не связанная с другими вершинами графа.
• Петля – ребро от вершины к этой же вершине.
• Ориентированный граф – граф, в котором все ребра имеют направление, указывающее, какая из вершин ребра является начальной, а какая – конечной.
• Неориентированный граф – граф, в котором у ребер нет направлений.
• Взвешенный граф – все ребра графа имеют веса.
• Невзвешенный граф – ребра графа не имеют весов.

1. Поиск в ширину

Обход или поиск – одна из основных операций, которую можно провести на графе. При поиске в ширину мы начинаем с определенной вершины и исследуем всех ее соседей на том же уровне, прежде чем переходить к следующему уровню.

В отличие от деревьев, графы могут содержать циклы (пути, в которых начальная и конечная вершины совпадают), так что нам придется отслеживать вершины, которые мы посетили. Реализуя поиск в ширину, обычно используют структуру данных очередь.

Рис. 2. Анимация поиска в ширину

Этот рисунок изображает поиск в ширину на примере графа. Обратите внимание, как вершины обнаруживаются (желтый цвет) и посещаются (красный).

Приложения. Поиск в ширину используется:

• для обнаружения кратчайших путей и минимальных покрывающих деревьев;
• поисковыми системами для построения индексов веб-страниц;
• для поиска в социальных сетях;
• для нахождения доступных соседних узлов в одноранговых сетях вроде BitTorrent.

2. Поиск в глубину

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

Рис. 3. Анимация поиска в глубину

Рис. 3 изображает поиск в глубину на примере того же графа. Обратите внимание, как он доходит до конца и возвращается назад.

Приложения. Поиск в глубину используется:

• для нахождения пути между двумя вершинами;
• для обнаружения циклов в графе;
• для топологической сортировки;
• для решения головоломок, имеющих только одно решение (например, лабиринтов).

3. Кратчайший путь

Кратчайший путь от одной вершины графа до другой – это путь, имеющий минимальный суммарный вес входящих в него ребер. Следующий рисунок показывает минимальный путь от вершины 1 к вершине 6.

Рис. 4. Анимация процесса нахождения минимального пути

Алгоритмы:

1. Алгоритм Дейкстры поиска минимального пути.
2. Алгоритм Беллмана-Форда.

Приложения. Поиск кратчайшего пути используется:

• для построения маршрута в приложениях вроде Google Maps;
• при создании компьютерных сетей – чтобы обеспечить минимальную задержку;
• в абстрактных автоматах для определения оптимальной стратегии достижения некоторой цели через несколько промежуточных состояний (например, для подсчета, сколько нужно ходов для победы в игре).

4. Обнаружение циклов

Цикл – это путь в графе, у которого начальная и конечная вершины совпадают. Если мы начинаем движение с некоторой вершины, и в конце концов возвращаемся к ней же, то этот путь – цикл. Обнаружение циклов – это процесс нахождения таких циклов. На рисунке показан обход цикла.

Рис. 5. Цикл

Алгоритмы:

1. Алгоритм Флойда для обнаружения циклов.
2. Алгоритм Брента.

Приложения. Обнаружение циклов используется:

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

5. Минимальное покрывающее дерево

Минимальное покрывающее дерево – это подмножество ребер графа, соединяющих все его вершины, имеющее минимальную сумму весов и не содержащее циклов. На рисунке показан процесс получения минимального покрывающего дерева.

Рис. 6. Анимация процесса нахождения минимального покрывающего дерева

Алгоритмы:

1. Алгоритм Прима.
2. Алгоритм Краскала.

Приложения. Минимальные покрывающие деревья используются:

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

6. Сильно связанные компоненты

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

Рис. 7. Сильно связанные компоненты

Алгоритмы:

1. Алгоритм Косараджу.
2. Алгоритм Тарьяна поиска сильно связанных компонентов.

Приложения. Сильно связанные компоненты используются:

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

7. Топологическая сортировка

Топологическая сортировка графа – это линейное упорядочение вершин графа таким образом, чтобы для каждого направленного ребра графа (u, v) вершина u в списке сортировки стояла перед v. На Рис. 8 изображен пример топологической сортировки вершин (1, 2, 3, 5, 4, 6, 7, 8). Показано, что вершина 5 должна следовать после вершин 2 и 3, а вершина 6 – после вершин 4 и 5.

Рис. 8. Топологическая сортировка вершин графа

Алгоритмы:

1. Алгоритм Кана.
2. Алгоритм, основанный на поиске в глубину.

Приложения. Топологическая сортировка используется:

• для выработки расписания инструкций;
• при сериализации данных;
• для определения порядка выполнения задач компиляции;
• для разрешения зависимостей символов при сборке (linking).

8. Раскраска графа

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

Хроматическое число графа – это минимальное количество цветов, необходимое для его раскраски. На рисунке изображена раскраска вершин графа четырьмя цветами.

Рис. 9. Раскраска вершин графа

Алгоритмы:

1. Алгоритмы, использующие поиск в ширину или в глубину.
2. «Жадная» раскраска.

Приложения. Раскраска графов используется:

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

9. Задача о максимальном потоке

Мы можем изобразить сеть потоков в виде графа, веса ребер которого будут соответствовать максимальной пропускной способности потока. В задаче о максимальном потоке требуется найти путь потока, обеспечивающий максимальную пропускную способность.

На рисунке показан пример определения максимального потока сети и нахождения итогового значения потока.

Рис. 10. Нахождение максимального потока

Алгоритмы:

1. Алгоритм Форда-Фалкерсона.
2. Алгоритм Эдмондса-Карпа.
3. Алгоритм Диница.

Приложения. Задача о максимальном потоке используется:

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

10. Соответствия

Соответствием в графе называется набор ребер, не имеющих общих вершин – то есть, никакие два ребра не имеют одну и ту же вершину. Соответствие называется максимальным, если оно содержит максимально возможное количество ребер, затрагивающих как можно больше вершин.

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

Рис. 11. Поиск соответствия в двухчастном графе

Алгоритмы:

1. Алгоритм Хопкрофта-Карпа.
2. Венгерский алгоритм.
3. Алгоритм сжатия цветков.

Приложения. Поиск соответствий используется:

• для определения соответствий вершин;
• в логистике для решения задач распределения ресурсов и оптимизации в пути.

Заключение

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

Если вы знакомы с Python, вы можете посмотреть, как алгоритмы на графах реализованы в модулях networkx и igraph.

M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне

При поиске кратчайшего пути на графах большого размера плохо работает традиционная оценка стоимости т.к. данные заведомо не помещаются в памяти и общая стоимость больше зависит от числа обращений к диску нежели от числа просмотренных рёбер. А число дисковых операций — весьма субъективный фактор, зависимый от сложно формализуемой пригодности графа к хранению на диске в форме удобной для конкретного алгоритма. Кроме того, очень важным становится компактность — количество информации в расчете на ребро и вершину.

Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.

Итак, наша задача — построение кратчайшего пути по графу из точки в точку. При этом граф достаточно велик, чтобы мы не имели возможности держать его целиком в памяти, а также невозможен предрасчет по сколь-нибудь значительному количеству вершин. Отличный образец — дорожный граф OSM. На данный момент число вершин в OSM превысило 4.6 млрд, общее число объектов — 400 млн.

Понятно, что в таких условиях поиск более-менее протяженного маршрута чистым алгоритмом Дейкстры или Левита невозможен в силу того, что мы не располагаем количеством памяти, необходимым для хранения промежуточных данных.

Как поступает алгоритм Дейкстры?

1. Заносим в приоритетную очередь стартовую точку с нулевой стоимостью.
2. Пока в очереди что-то есть — пусть вершина V, для каждого исходящего ребра (E), которое мы до сих пор не просматривали:
   1. проверяем что это не искомое ребро, если да, то конец;
   2. подсчитываем стоимость прохода E;
   3. и заносим конечную вершину ребра E в очередь со стоимостью её достижения — стоимость достижения V + стоимость E.

В результате для разреженных (например, геометрических) графов получаем стоимость O(n*log(n) + m*log(n)), где n-число просмотренных вершин, m-число просмотренных ребер.

Фиг.1 Здесь мы видим найденный маршрут и просмотренные при этом ребра.

Проблема в том, что алгоритм Дейкстры не использует никакой информации о свойствах графа и искомого маршрута и при его работе (распространении т.н. «волны») периметр этой «волны» движется от искомой точки во всех направлениях без какой-либо дискриминации.

С другой стороны, на геометрических графах, например, развитой дорожной сети, есть смысл стимулировать распространение «волны» по направлению к цели и штрафовать за остальные направления. Эта идея реализована в алгоритме A*, который является обобщением алгоритма Дейкстры.

В A* стоимость вершины при помещении её в приоритетную очередь не просто равна пройденному пути, а включает еще и оценку пути оставшегося. Как нам получить эту оценку?

Стоит отметить, что это должны быть достаточно вычислительно-дешевая оценка т.к. выполняется она большое число раз. Первое что приходит в голову — вычислить геометрическое расстояние от текущей точки до финиша и исходить из этого, например: осталось 10 км — средняя скорость при движении по городу 20 км/ч, значит наша оценка — полчаса.

При этом, если ребро ведет нас по направлению к финишу, оценка для него будет уменьшаться и компенсировать пройденный путь.

Для ребер, ведущих от цели, эта оценка станет расти, в результате такие точки попадут в очередь с большим весом и вполне вероятно, что до них дело так и не дойдёт.

Примерно такого же эффекта можно достичь, кстати, с помощью техники Beam Search, где принудительно ограничивается размер приоритетной очереди и «недостойные» с точки зрения эвристики кандидаты просто отбрасываются.

Фиг.2 Здесь мы видим поиск того же маршрута с использованием описанной эвристики, почувствуйте разницу.

A* превращается в алгоритм Дейкстры если оценка стоимости возвращает 0, как если бы мы считали, что остаток пути промчимся с бесконечной скоростью.

A* относится т.н. информированным алгоритмам т.к. в эвристике мы используем предположение, что движение в направлении цели скорее приведёт нас к успеху.

Каковы должны быть свойства функции оценки? Она должна быть правдоподобной. Как мы уже выяснили, слишком оптимистичная оценка сводит на нет наши попытки уменьшить просматриваемую часть графа. С другой стороны, слишком пессимистичная оценка заставит алгоритм построить путь строго по направлению, невзирая ни на что. Вряд ли это нас устроит.

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

Но тут сразу возникает масса нюансов:

• Как определить что мы в городе? Это не так уж и дешево.
• А ничего, что большая часть городов построена на реках?
• В городе разные участки дорог могут быть загружены сильно по разному.
• А если мы должны проехать через множество городов и рек?

Можно использовать и разные эвристики в духе метода ветвей и границ:

1. Находим путь с очень пессимистичной эвристикой, из чего следует, что, предположительно, есть и более эффективные маршруты.
2. Теперь мы будем использовать стоимость найденного маршрута как оценку сверху, просто не включая в приоритетную очередь претендентов, которые заведомо не могут дать нам маршрут более эффективный, чем уже найденный.
3. Делаем оценку менее пессимистичной и вновь строим маршрут с верхней границей стоимости.
4. Получаем новую оценку.
5. Продолжаем так до тех пор, пока не получим удовлетворительное решение.

Есть еще одна проблема с оценкой стоимости, о которой нельзя не упомянуть.

В жизни геометрически близкие объекты могут быть достаточно удаленными с точки зрения дорожного графа. Например, находиться на разных сторонах реки, горной гряды, моря… В таком случае оценка, основанная на геометрической близости начнёт усугублять ситуацию, упорно направляя «волну» в неправильном направлении.

Фиг.3 Вот так выглядит просмотренная A* часть графа OSM для поиска пути из Италии в Албанию.

Впрочем, это всё равно лучше чем алгоритмом Дейкстры. Хорошо видно как заполнив всю Италию, «волна» начала переливаться через край, набрала скорость и быстро достигла цели.

Фиг.4 А вот так выглядит просмотренная часть графа для алгоритма Дейкстры. По сравнению с ней всё не так уж и мрачно.

А можно ли еще как-то улучшить алгоритм, что по этому поводу говорит Сomputer Sience?

Двунаправленный поиск

Можно пустить две A* волны навстречу друг другу. Это называется bidirectional search и на первый взгляд кажется очень привлекательной идеей. В самом деле, при хорошей транспортной связности “волна” представляет собой эллипсоид, две малых волны, пущенные навстречу, заметут меньшую площадь по сравнению с одной большой. С другой стороны, возникает проблема обнаружения встречи «волн», точек в их периметрах может быть довольно много и проверять на каждом шагу наличие ребра в чужом периметре не так уж и дешево.

Фиг.5 встречные волны Дейкстры

Возможно, с этим можно было бы и смириться при реальном выигрыше в объеме просмотренной части графа. Но вот если мы рассмотрим вышеописанный пример поиска проезда из Италии в Албанию, то обнаружим, что двунаправленный поиск нам ничем не поможет, а только усугубит ситуацию т.к. кроме заливки всей Италии мы вынуждены будем просмотреть и всю Грецию с половиной Балкан, прежде чем волны встретятся. Ибо вместо одной «волны», упёршейся в препятствие, будем иметь две таковых.

Иерархические подходы

Использование иерархии дорог

Некоторые коммерческие системы, например StreetMap USA, используют для роутинга тот факт, что хорошо спланированная дорожная сеть имеет двухуровневую природу — есть сеть местных дорог и (значительно меньшая) сеть шоссе для поездок на дальние расстояния. Представляется естественным использовать этот факт. Вводятся шлюзы (transit nodes) — вершины, на которых происходит переход из одного уровня в другой. Нахождение “достаточно длинного” пути сводится к нахождению путей от:

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

Фиг.6 Кусочек StreetMap

Выгоды такого подхода очевидны. Минусы таковы:

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

Построение иерархии графа

Если нет возможности и/или желания выверять граф, остаётся возможность построить иерархию автоматически.

Так или иначе, эксплуатируется идея, что хоть граф и не выверен, тем не менее, атрибуты рёбер позволяют строить маршруты приемлемого качества. Но в силу размеров графа, построение тем же A* в рабочем режиме непозволительно дорого.

Например, это может выглядеть так:

• на этапе предрасчета выбирается множество (пусть даже случайных) вершин;
• для пар пространственно удаленных вершин обычным A* строятся кратчайшие маршруты;
• на основе построенных маршрутов ведётся статистика пройденных рёбер;
• после того, как набралось достаточное количество данных, посещенные рёбра объявляются следующим уровнем иерархии;
• последовательно идущие рёбра без ветвлений сливаются в «макрорёбра» с сохранением стоимости проезда;

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

Маршрутизация в таком иерархическом графе осуществляется двунаправленным поиском (A* или алгоритмом Дейкстры).

Сепараторы

Основной идеей метода является попытка разделения графа на компоненты путём удаления небольшой части ребер — сепараторов. Эти сепараторы и предварительно вычисленные пути между ними образуют следующую иерархию. Утверждается [1], что затратив O(n*log(n)**3) времени и пространства на диске для предварительного расчета, можно выполнять запросы за O(sqrt(n)*log(n))

Grid Based Transit Nodes

Это в общем та же идея с сепараторами, но в целях масштабирования и простоты граф делится на фрагменты решеткой или квадро-деревом, ребра, которые пересекают границы фрагментов становятся транзитными. Понятно, что цена этому — эффективность. В плюсах — высокая автоматизация и как следствие отсутствие человеческого фактора.

Таблицы расстояний

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

Фиг.7 [1]

Reach [3]

Идея метода такова — замечено, что при построении длинных оптимальных маршрутов, «локальные» рёбра посещаются только в самом начале или конце маршрута. Следовательно, построив некоторое количество «обучающих» длинных маршрутов, можно понять, насколько близко расположено то или иное ребро к любому из концов маршрута.

Для некоторого обучающего маршрута P(s…..u.v……t) вводится показатель reach — минимальное расстояние до концов reach(uv) = min(dist(s…..u), dist(v…..t)).

На всём обучающем множестве reach(uv) — максимальное значение на всех маршрутах, где встретилось ребро (uv).

При «боевом» поиске мы вдали от старта и финиша просто будем стараться избегать рёбер с маленьким значением reach.

Фиг.8 [21]

Идея метода очень красивая, вопросы вызывает лишь качество обучающей выборки, её достаточность и ресурсы, потраченные на обучение.

Целеустремленные алгоритмы

Arc-Flags [4]

Граф делится на фрагменты. Проводится обучение построением кратчайших маршрутов между предопределенными точками. При построении обучающего пути, для каждого ребра сохраняется факт, что через него проходит кратчайший маршрут в клетку финальной точки.

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

Специфические недостатки этого метода видны невооруженным взглядом:

• Количество фрагментов графа не может быть велико, 8К фрагментов (что не так уж и много) дадут нам (предположительно несжимаемый) килобайт на каждое ребро. Sic!
• Надо быть очень осторожным с нарезкой фрагментов, внутри фрагмента граф должен быть связным.

ALT [5]

Из всех вершин выбирается небольшое количество landmarks: λ. В изначальном варианте для каждой вершины предварительно рассчитывались стоимости до каждого λ. Это требовало колоссального количества дополнительной памяти и в дальнейшем требования смягчились и вершины стали группировать.

Поиск в ALT осуществляется как в A*, но оценка оставшегося пути делается на основе рассчитанных стоимостей. Пусть мы рассматриваем ребро (u,v) на пути к целевой вершине t. Для каждой λ в соответствии с неравенством треугольника мы имеем оценку оставшейся части пути (через λ): dist(λ, t) − dist(λ, v) ≤ dist(v, t) и dist(v, λ) − dist(t, λ) ≤ dist(v, t). Минимум для всех λ и даст искомую оценку.

Фиг.9

Предварительные итоги

Мы видим два основных направления, в которых идёт развитие:

1. Иерархии. Позволяют весьма эффективно строить пути на больших расстояниях в структурированных графах. Но на маленьких расстояниях дешевле пользоваться обычным A* или Дейкстрой. Следовательно существует “серая” область, где оба алгоритма работают посредственно.

   Кроме того, на аморфных графах попытка построить иерархию может лишь привести к проблемам. Представим себе граф в виде прямоугольной решетки из равнозначных дорог. При движении в некотором направлении правильным решением будет поворачивать в случайном направлении с вероятностью, связанной с направлением. Т.е. если азимут к цели составляет 45°, стоит с равной вероятностью поворачивать направо и налево, чтобы не создавать пробок.

   Попытка же построить на такой сетке иерархию приведет к тому, что дорожная сеть станет использоваться неэффективно.

2. Использование внутренней природы графа для принятия решения о направлении движения к цели. Идея выглядит многообещающей, но вызывает много вопросов. Основная проблема — человеческий фактор. Что lanmark’и, что фрагменты Arc-Flags требуют участия эксперта, если пустить их определение на самотёк, легко можно получить не то, что доктор прописал.

   Кроме того, требуется (нелинейное от размера графа) количество дополнительной памяти.

Вот «если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколь-нибудь развязности, какая у Балтазара Балтазаровича, да, пожалуй…» ©

Справедливости ради стоит сказать, что таких попыток немало, некоторые из них можно найти в списке источников данной статьи. Но мы, конечно же, не изменим себе и придумаем свой собственный, «не имеющий аналогов» метод. ️

Эвристика

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

Идея восходит к этой работе.

• Раз уж мы работаем с OSM, масштаб графа — вся планета.
• Разобьем пространство сеткой в 1°, да, это даёт искажения к полюсам, но мы ведь разрабатываем всего лишь оценку.
• При построении графа будем растеризовать пути на этой сетке, допустим, для 2-го переулка Крупской в Новосибирске мы должны пометить клеточку, соответствующую 55°с.ш. и 82°в.д.
• После растеризации всех известных нам дорог, получим карту населенности с точностью до градуса.

  Фиг.10 — число дорог на квадратный градус в логарифмической шкале

• Будем рассматривать нашу карту как граф, где населенные клеточки — вершины.
• Будем считать, что если соседние клеточки населены, то это ребро, из одной можно проехать в другую, стоимость прямого проезда — 111 км на экваторе, стоимость проезда наискосок умножается на корень из 2.
• Если в этом графе мы запустим волну в соответствии с алгоритмом Дейкстры, запоминая стоимость достижения каждой вершины, это даст нам оценку стоимости пути до финиша в любой достижимой точке. Например, если пустить волну из Новосибирска, это будет выглядеть так:

  Фиг.11 Оценка стоимости проезда из Нск, чем ближе к оранжевому, тем длинней путь.

Итак, для поиска:

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

Но ведь градус — это довольно грубая сетка, некоторые проливы могут слипнуться, например, «маленький остров» с Нормандией.

Не беда, в OSM есть тип — береговая линия. Мы растеризуем береговые линии и разрешим ходить из клетки, помеченной как прибрежная, только на «материковые» клетки.

Фиг.12 Береговая линия OSM

Но тут выясняется, что:

• береговая линия есть не везде;
• Япония и др. целиком состоит из прибрежных клеток;
• Гибралтар и Танжер оказались в одной клетке;
• …

Ок, придется руками нарисовать разделительные линии в важных проливах, растеризовать их и запрещать пересекать при распространении волны.

Благо, это одноразовая работа, а таких проливов не очень много.

Вот, например, распространение «волны» из Италии, обратим внимание на Гибралтарский пролив.

Фиг.13 Оценка стоимости проезда в Италию, чем ближе к оранжевому, тем длиннее путь.

В целом схема приемлема, но:

1. она требует ручной работы;
2. ручной работы много;
3. надо быть очень осторожным, если на одну клетку легло несколько разделительных линий.

Возможно, здесь хорошо сработает вариант, когда каждая «прибрежная» клетка представлена квадро-деревом, распространение волны следует проводить и по элементам квадродерева.

Но всё же чувствуется во всём этом какая-то натяжка, поэтому в дело вступает План Б.

План Б.

1. Пусть мы имеем вышестоящий уровень иерархию графа, полученный, например, способом, описанным в разделе «построение иерархии графа».
2. Этот уровень достаточно груб для того, чтобы поиск на любые расстояния в нем не представлял проблем.
3. Итак, мы имеем на руках путь, построенный на более высоком уровне иерархии графа.

   Фиг.14 Путь, проложенный по верхнеуровневому графу.

4. Нанесем на этот маршрут опорные точки, например, через каждые 500 км, включая финиш, конечно

   Фиг.15 Опорные точки.

5. Для каждой опорной точки мы знаем остаток пути от неё до финиша. Теперь эвристика остатка пути для A* будет состоять из двух частей:
   1. геометрического расстояния до текущей опорной точки;
   2. остаток пути от текущей опорной точки до финиша.

6. В начале поиска текущей назначается первая опорная точка. Как только ма приближаемся к ней на геометрическое расстояние ближе чем 200 км (условно, конечно), начинаем ориентироваться на следующую опорную точку. И так до самого финиша.
7. Результат таков:

   Фиг. 11 Хорошо видно, как волна начинает расползаться вширь, когда опорный путь резко меняет направление. Тем не менее, общий объем прочитанных данных весьма невелик. Наблюдается также ускорение в ~20 раз.

8. Больше всего эта техника напоминает изображение из шапки к данной статье. Поэтому автор и дал ей название M* («M» значит «морковка»).

Выводы

Итак, на суд читателя представлены два варианта эвристики подсчета стоимости остатка пути для A*.

Для обоих вариантов:

• проверена их работоспособность на практике;
• скорость работы A* примерно одинакова, для указанного пути это 4.5 сек (рядовой десктоп) с чтением и распаковкой данных, 0.5 сек — только проход волны на разогретом кэше;
• количество дополнительно хранимой информации минимально — 0.2% для второго варианта, для первого еще меньше;
• т.к. A* работает с исходным графом, нет никаких препятствий к использованию временных ограничений, например, паромов, разводных мостов, данных о пробках…

Как бы то ни было, это еще один инструмент для работы с графами, весьма полезный в условиях ограниченных ресурсов и/или неограниченных данных. В частности, никто не запрещает использовать эту же технику для двустороннего поиска.Источники[1] Robust, Almost Constant Time Shortest-Path Queries in Road Networks⋆

Peter Sanders and Dominik Schultes

[2] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm

Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner

[3] R. J. Gutman. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In Proceedings of the 6th Workshop on Algorithm Engineering, 2004

[4] E. Köhler, R. H. Möhring, and H. Schilling. Acceleration of Shortest Path and Constrained

Shortest Path Computation. In Proceedings of the 4th Workshop on Experimental Algorithms

(WEA’05), Lecture Notes in Computer Science, pages 126–138. Springer, 2005.

[5] Goldberg, A.V., Werneck, R.F.: Computing Point-to-Point Shortest Paths from External Memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 26–40. SIAM (2005)

[6] Defining and Computing Alternative Routes in Road Networks

Jonathan Dees, Robert Geisberger, and Peter Sanders

[7] Alternative Routes in Road Networks

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

[8] Partitioning Graphs to Speedup Dijkstra’s Algorithm

ROLF H. MOHRING and HEIKO SCHILLING

[9] SHARC: Fast and Robust Unidirectional Routing

Reinhard Bauer Daniel Delling

[10] Cambridge Vehicle Information Technology Ltd. Choice Routing

[11] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm?

Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner

[12] Fast and Exact Shortest Path Queries Using Highway Hierarchies

Dominik Schultes

[13] Engineering Highway Hierarchies

Peter Sanders and Dominik Schultes

[14] Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling

[15] Dynamic Highway-Node Routing

Dominik Schultes and Peter Sanders

[16] A FAST AND HIGH QUALITY MULTILEVEL SCHEME FOR PARTITIONING IRREGULAR GRAPHS

GEORGE KARYPIS AND VIPIN KUMAR

[17] Multilevel Algorithms for Partitioning Power-Law Graphs

Amine Abou-rjeili and George Karypis

[18] Impact of Shortcuts on Speedup Techniques?

Reinhard Bauer, Daniel Delling, and Dorothea Wagner

[19] Transit Node Routing based on Highway Hierarchies

Peter Sanders Dominik Schultes

[20] In Transit to Constant Time Shortest-Path Queries in Road Networks∗

Holger Bast Stefan Funke Domagoj Matijevic Peter Sanders Dominik Schultes

[21] Reach for A∗: an Efficient Point-to-Point Shortest Path Algorithm Andrew V. Goldberg

PS: статья по результатам доклада на DUMP 2017

Алгоритм Беллмана-Форда / Блог компании OTUS. Онлайн-образование / Хабр

В преддверии старта курса «Алгоритмы для разработчиков» подготовили очередной перевод интересной статьи.

Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе. В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи). Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.

Алгоритм

Ниже приведены подробно расписанные шаги.

Входные данные: Граф и начальная вершина src.
Выходные данные: Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.

1. На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src], где src — исходная вершина.
2. Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V|-1 раз, где |V| — число вершин в данном графе.
   • Произведите следующее действие для каждого ребра u-v:
     
     Если dist[v] > dist[u] + вес ребра uv, то обновите dist[v]
dist [v] = dist [u] + вес ребра uv

3. На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:
   • Если dist[v] > dist[u] + вес ребра uv, то в графе присутствует цикл отрицательного веса.

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

Как это работает? Как и в других задачах динамического программирования, алгоритм вычисляет кратчайшие пути снизу вверх. Сначала он вычисляет самые короткие расстояния, то есть пути длиной не более, чем в одно ребро. Затем он вычисляет кратчайшие пути длиной не более двух ребер и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути длиной не более i ребер. В любом простом пути может быть максимум |V|-1 ребер, поэтому внешний цикл выполняется именно |V|-1 раз. Идея заключается в том, что если мы вычислили кратчайший путь с не более чем i ребрами, то итерация по всем ребрам гарантирует получение кратчайшего пути с не более чем i + 1 ребрами (доказательство довольно простое, вы можете сослаться на эту лекцию или видеолекцию от MIT)

Пример

Давайте разберемся в алгоритме на следующем примере графа. Изображения взяты отсюда.
Пусть начальная вершина равна 0. Примите все расстояния за бесконечные, кроме расстояния до самой src. Общее число вершин в графе равно 5, поэтому все ребра нужно пройти 4 раза.

Пусть ребра отрабатываются в следующем порядке: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Мы получаем следующие расстояния, когда проход по ребрам был совершен первый раз. Первая строка показывает начальные расстояния, вторая строка показывает расстояния, когда ребра (B, E), (D, B), (B, D) и (A, B) обрабатываются. Третья строка показывает расстояние при обработке (A, C). Четвертая строка показывает, что происходит, когда обрабатываются (D, C), (B, C) и (E, D).

Первая итерация гарантирует, что все самые короткие пути будут не длиннее пути в 1 ребро. Мы получаем следующие расстояния, когда будет совершен второй проход по всем ребрам (в последней строке показаны конечные значения).

Вторая итерация гарантирует, что все кратчайшие пути будут иметь длину не более 2 ребер. Алгоритм проходит по всем ребрам еще 2 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют значения расстояний.

Реализация:

# Python program for Bellman-Ford's single source 
# shortest path algorithm. 

from collections import defaultdict 

# Class to represent a graph 
class Graph: 

	def __init__(self, vertices): 
		self.V = vertices # No. of vertices 
		self.graph = [] # default dictionary to store graph 

	# function to add an edge to graph 
	def addEdge(self, u, v, w): 
		self.graph.append([u, v, w]) 
		
	# utility function used to print the solution 
	def printArr(self, dist): 
		print("Vertex Distance from Source") 
		for i in range(self.V): 
			print("% d \t\t % d" % (i, dist[i])) 
	
	# The main function that finds shortest distances from src to 
	# all other vertices using Bellman-Ford algorithm. The function 
	# also detects negative weight cycle 
	def BellmanFord(self, src): 

		# Step 1: Initialize distances from src to all other vertices 
		# as INFINITE 
		dist = [float("Inf")] * self.V 
		dist[src] = 0


		# Step 2: Relax all edges |V| - 1 times. A simple shortest 
		# path from src to any other vertex can have at-most |V| - 1 
		# edges 
		for i in range(self.V - 1): 
			# Update dist value and parent index of the adjacent vertices of 
			# the picked vertex. Consider only those vertices which are still in 
			# queue 
			for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						dist[v] = dist[u] + w 

		# Step 3: check for negative-weight cycles. The above step 
		# guarantees shortest distances if graph doesn't contain 
		# negative weight cycle. If we get a shorter path, then there 
		# is a cycle. 

		for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						print "Graph contains negative weight cycle"
						return
						
		# print all distance 
		self.printArr(dist) 

g = Graph(5) 
g.addEdge(0, 1, -1) 
g.addEdge(0, 2, 4) 
g.addEdge(1, 2, 3) 
g.addEdge(1, 3, 2) 
g.addEdge(1, 4, 2) 
g.addEdge(3, 2, 5) 
g.addEdge(3, 1, 1) 
g.addEdge(4, 3, -3) 

# Print the solution 
g.BellmanFord(0) 

# This code is contributed by Neelam Yadav 

Выходные значения:

Примечания:

1. Отрицательные веса встречаются в различных применениях графов. Например, вместо того чтобы увеличивать стоимость пути, мы можем получить выгоду, следуя по определенному пути.
2. Алгоритм Беллмана-Форда работает лучше для распределенных систем (лучше, чем алгоритм Дейкстры). В отличие от Дейкстры, где нам нужно найти минимальное значение всех вершин, в Беллмане-Форде ребра рассматриваются по одному.

Упражнения:

1. Стандартный алгоритм Беллмана-Форда сообщает кратчайшие пути только в том случае, если в нем нет циклов отрицательного веса. Измените его таким образом, чтобы он сообщал о кратчайших путях даже при наличии такого цикла.
2. Можем ли мы использовать алгоритм Дейкстры для поиска кратчайших путей в графе с отрицательными весами? Есть такая идея: вычислить минимальное значение веса, прибавить положительное значение (равное модулю значения минимального веса) ко всем весам и запустить алгоритм Дейкстры для модифицированного графа. Сработает ли такой алгоритм?

Простая реализация алгоритма Беллмана-Форда

Источники:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath3.prn.pdf

Создайте график онлайн и найдите кратчайший путь или используйте другой алгоритм.

Создайте график и найдите кратчайший путь. На странице справки вы найдете обучающее видео.

Установить матрицу смежности. Используйте запятую «,» в качестве разделителя

Матрица мультиграфа содержит вес минимальных ребер между вершинами.

Матрица неверна. Используйте запятую «,» в качестве разделителя. Матрица должна быть квадратной

Установите матрицу инцидентности.Используйте запятую «,» в качестве разделителя.

Матрица неверна. Используйте запятую «,» в качестве разделителя.

Ваш алгоритм отправлен на проверку и в случае успеха будет добавлен на сайт.

Невозможно создать график. Матрица смежности имеет неправильный формат. Нажмите кнопку «исправить матрицу», чтобы исправить матрицу, или кнопку «справка», чтобы открыть справку о формате матрицы смежности

Невозможно создать график. Матрица заболеваемости имеет неправильный формат. Нажмите кнопку «исправить матрицу», чтобы исправить матрицу, или кнопку «справка», чтобы открыть справку о формате матрицы заболеваемости

Выделяйте и перемещайте объекты мышью или перемещайте рабочее пространство.

Перетащите курсор для перемещения объектов

Выделяйте и перемещайте объекты мышью или перемещайте рабочее пространство.

Перетащите курсор для перемещения объектов

Щелкните в рабочей области, чтобы добавить новую вершину. Перечисление вершин

Выбрать первую вершину ребра

Выбрать вторую вершину ребра

Выбрать начальную вершину кратчайшего пути

Выбрать конечную вершину кратчайшего пути

Наименьшая длина пути% d

Путь не существует

Нажмите на объект, чтобы удалить

Добавить край

Направленный

Неориентированный

Матрица смежности

Сохранить

Отмена

наименьшее расстояние

Матрица заболеваемости

График сохранения

закрыть

Количество подключаемых компонентов

Количество слабосвязных компонент

Что вы думаете о сайте?

Имя (адрес электронной почты для обратной связи)

Обратная связь

Отправить

Чтобы задать нам вопрос или отправить комментарий, напишите нам по телефону

исправить матрицу

справка

Матрица имеет неправильный формат

Сохранить изображение графика

Полный отчет

Краткое сообщение

График не имеет эйлерова цикла

График имеет эйлеров цикл

Обработка…

Добавить вершину

Переименовать вершину

Переименовать

и

Изменить вес

не имеет веса

Переименовать группу

Голосовать

Рекомендовать алгоритмы

График не имеет эйлерова пути

График имеет эйлеров путь

График минимальных расстояний

Отметьте, чтобы сэкономить

Показать матрицу расстояний

Матрица расстояний

Выберите источник максимального расхода

Выбрать мойку максимального расхода

Максимальный расход от% 2 до% 3 равен% 1

Поток из% 1 в% 2 не существует

Источник

Мойка

Граф не имеет гамильтонова цикла

Граф имеет гамильтонов цикл

График не имеет гамильтонова траектория

График имеет гамильтонов путь

Выбрать начальную вершину обхода

Порядок обхода:

Отвод края

Отменить

Сохранить график

По умолчанию

Vertex Style

Edge Style

Цвет фона

Multigraph поддерживает не все алгоритмы

не имеет веса

Используйте Cmd⌘ для выбора нескольких объектов.

Используйте Ctrl для выбора нескольких объектов.

Перетащите группу.

Группа копий

Удалить группу

Поиск в ширину

Раскраска графика

Найти подключенные компоненты

Поиск в глубину

Найдите цикл Эйлера

Найдите эйлеров путь

Алгоритм Флойда – Уоршалла

Упорядочить график

Найти гамильтонов цикл

Найти гамильтонов путь

Найти максимальный расход

Поиск минимального остовного дерева

Визуализация по весу

Радиус и диаметр поисковой диаграммы

Найдите кратчайший путь с помощью алгоритма Дейкстры

Вычислить степень вершин

Масса минимального остовного дерева

Во время расчета мы игнорировали направление ребер.

График отключен

.

Кратчайший путь в неориентированном графе, который посещает k вершин

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

.