Поиск кратчайшего пути


Содержание

Поиск кратчайшего пути

БлогNot. C++: поиск кратчайшего пути на графе

C++: поиск кратчайшего пути на графе

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

Граф представляет собой сеть из узлов-«городов» и соединяющих их путей-«дорог», при этом каждая «дорога» может иметь свой вес, соответствующий «расстоянию» между узлами, ну или «стоимости перевозки» между ними. Например, изображённый без весов граф может быть таким (все веса приняты за единицу):

Для описания одного пути подходит описанная в программе простая структура item , а весь граф — это просто массив map , состоящий из элементов item . Ещё проще было бы разместить всю информацию в матрице A размером n*n ( n = числу узлов графа), каждый ненулевой элемент которой Ai,j соответствует весу пути из i-ой вершины в j-ую, но большинство элементов в такой матрице будут нулями, и она мне кажется избыточной.

Вот консольная реализация для Visual Studio 2010 или выше:

1. Нумерация узлов сделана с нуля, как принято в C++;

2. Если искомых путей с одинаковым общим весом len несколько, будет возвращён тот, что найден первым при лексикографическом (по номерам) порядке обхода вершин, например, 4-5-6, но не 4-7-6;

3. В тесте все веса одинаковы и равны 1, но должно работать и при разных;

4. Все пути предполагаются двусторонними, то есть, если есть дорога из i в j , то она есть и имеет тот же вес и из j в i . Если это не так, измените логику метода find :

15.06.2015, 10:31; рейтинг: 16375

Кратчайший путь в ациклическом графе

Задача:
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из [math]u[/math] в [math]v[/math] .

Содержание

Решение [ править ]

Воспользуемся принципом оптимальности на префиксе.
Пусть [math]d[/math] — функция, где [math]d(i)[/math] — вес кратчайшего пути из [math]u[/math] в [math]i[/math] . Ясно, что [math]d(u)[/math] равен [math]0[/math] . Пусть [math]w(i, j)[/math] — вес ребра из [math]i[/math] в [math]j[/math] . Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения:

Так как мы обходим граф в порядке топологической сортировки, то на [math]i[/math] -ом шаге всем [math]d(j)[/math] ( [math]j[/math] такие, что существует ребро из [math]j[/math] в [math]i[/math] ) уже присвоены оптимальные ответы, и, следовательно, [math]d(i)[/math] также будет присвоен оптимальный ответ.

Реализация [ править ]

Реализуем данный алгоритм:

Пример [ править ]

Пусть дана матрица смежности графа [math]w[/math] со следующими весами ребер:

1 2 3 4 5 6 7 8
1 2
2 1 1 4 3
3 1
4
5 3 1
6 5 2
7 2
8 1

Требуется найти вес кратчайшего пути из 2 в 4.
Массив [math]p[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]p[i][/math] 2 3 6 7 1 5 8 4

Массив [math]d[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]d[i][/math] 1 1 5 3 2 4 4

Ответ равен [math]5[/math] .

Альтернативный способ решения [ править ]

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

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

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

Рассматриваемый алгоритм иногда называют алгоритмом Флойда -Уоршелла. Алгоритм Флойда -Уоршелла является алгоритмом на графах, который разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа .

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

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

В алгоритме Флойда используется матрица A размером nxn , в которой вычисляются длины кратчайших путей . Элемент A[i,j] равен расстоянию от вершины i к вершине j , которое имеет конечное значение , если существует ребро (i,j) , и равен бесконечности в противном случае.

Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j], то целесообразно заменить путь i->j путем i->k->j . Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу расстояния A и матрицу последовательности вершин S . Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1 .

Основной шаг k . Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1 . Если выполняется неравенство

  1. создаем матрицу Ak путем замены в матрице Ak-1 элемента A[i,j] на сумму A[i,k]+A[k,j] ;
  2. создаем матрицу Sk путем замены в матрице Sk-1 элемента S[i,j] на k . Полагаем k = k + 1 и повторяем шаг k .

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

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

Если граф представлен матрицей смежности , то время выполнения этого алгоритма имеет порядок O(n 3 ) , поскольку в нем присутствуют вложенные друг в друга три цикла .

Переборные алгоритмы

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

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

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn . Элемент матрицы A[i,j]=0 , если клетка (i,j) проходима. В противном случае .

Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n) .

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

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

Перебор с возвратом

Данный метод основан на методе поиска в глубину . Перебор с возвратом считают методом проб и ошибок («попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую»). Так как перебор вариантов осуществляется методом поиска в глубину , то целесообразно во время работы алгоритма хранить текущий путь в дереве. Этот путь представляет собой стек Way.

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

Пусть текущей является некоторая клетка (в начале работы алгоритма – клетка (1, 1) ). Если для текущей клетки есть клетка-сосед Neighbor , отсутствующая в Way , в которую на этом пути еще не ходили, то добавляем Neighbor в Way и текущей клетке присваиваем Neighbor , иначе извлечь из Way .

Приведенное выше описание дает четко понять, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция «извлечь из Way «, которая уменьшает длину Way на 1.

Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда ( рис. 45.3).

Way является текущим путем, но в процессе работы необходимо хранить и оптимальный путь OptimalWay .

Усовершенствование алгоритма можно произвести следующим образом: не позволять, чтобы длина Way была больше или равна длине OptimalWay . В этом случае, если и будет найден какой-то вариант, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. Данное улучшение алгоритма позволяет во многих случаях сильно сократить перебор.

Поиск кратчайшего пути в графе

18.12.2011, 01:26

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

Поиск кратчайшего пути на графе
Выдает ошибку Error 1 error C4996: ‘itoa’: The POSIX name for this item is deprecated. Instead, use.

Восстановление кратчайшего пути в графе
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие.

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2.

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

18.12.2011, 11:06 [ТС] 2

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

Добавлено через 9 часов 40 минут
Ну помогите а?

18.12.2011, 11:15 3

Флойд, Дейкстра или Форд-Беллман. Надо только матрицу смежности построить.

Добавлено через 57 секунд

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

18.12.2011, 20:42 [ТС] 4

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

Добавлено через 55 минут
Готов заплатить через Яндекс деньги! Только помогите, завтра сдать надо эту штуку. Еще бы блоксхему бы.

Добавлено через 28 минут
неужели никто не возьмется? 300-450 рублей заплачу за задачу и блоксхему.

Добавлено через 1 час 7 минут
ну возмитесь кто нибудь, завтра сдавать нужно, а я вообще в непонятках как делать

18.12.2011, 20:42
18.12.2011, 20:51 5
18.12.2011, 20:53 [ТС] 6
18.12.2011, 20:58 7
18.12.2011, 21:18 [ТС] 8

Ну как сделать то мое задание знает кто нибудь? Плачу 400 р. (прога и блоксхема)

Добавлено через 18 минут
А все, не надо, кажется я все сделал)))

18.12.2011, 21:41 9

Флойд N^3
Дейкстра N^2
Дейкстра с кучей N*logN

Добавлено через 40 секунд
Иначе не было бы смысла в Дейкстре писать 20 строк, чем во Флойде 3

18.12.2011, 21:44 [ТС] 10

Народ, подойдет код для моего задания:

18.12.2011, 21:46 11
18.12.2011, 21:50 [ТС] 12
18.12.2011, 21:50 13
19.12.2011, 02:02 [ТС] 14

А как будет выглядить матрица смежности для графа?

Добавлено через 3 часа 46 минут
Можете мне написать матрицу смежности для моего графа, пожалуйста.
Я так понял что она будет 9×9 и ставится 1 если из одной точки можно попасть в другую, а если нельзя то 0.

19.12.2011, 08:25 15
вроде так:
0 1 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 0 0
0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 1 1 0
0 1 0 1 1 0 0 0 0
0 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 1 1 0
21.12.2011, 16:57 [ТС] 16

Народ, может вопрос не совсем по теме. Меня интересует как работает алгоритм Дейкстра на этом примере, я просто защищаю лабу уже второй раз подряд, заваливаюсь на одном и том же.
Вот как я ему объясняю: все расстояния между вершинами в начале равны бесконечности, начинаем из вершины м1, так как ей ничего не предшествует, кратчайший путь из м1 в м1 равен 0, потом идем дальше к вершине м2, записываем для нее расстояние от м1, допустим 1, и запоминаем для нее кратчайший путь. Далее из вершины м2 мы можем попасть в м3 или м6, идем в м3, так как логичнее сначала туда пойти, запоминаем расстояние и путь для нее, дальше у нас выбор между м5 и м4, идем в м4, запоминаем расстояние и путь для нее. а вот дальше все что бы я не говорил, он не воспринимал, и говорил, что все неправильно. Можете подсказать каким образом проходит алгоритм Дейкстра в этом графе и как мне все это преподу рассказать по шагам. Заранее спасибо)

Добавлено через 15 часов 0 минут
Ответьте, кто-нибудь..

12.04.2013, 14:21 17
12.04.2013, 14:21
12.04.2013, 14:21

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска.

Поиск кратчайшего пути
Как сделать что бы задача не считала стоимость проезда в обратную сторону ? #include .

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

§18 Алгоритмы на графах

Графы. Общие сведения

Из теории графов

Граф — это абстрактный объект, представляющий собой множество вершин (узлов) и набор рёбер – связей (соединений) между парами вершин. Тема графов очень обширна. Только терминологии графов посвящена цела страничка в Википедии [1]. Графы являются предметом изучения в дискретной математике (где дается более точное определение понятия графа). Графы применяются для описания сложно структурированной информации и, поэтому имеют огромное прикладное значение. Появлению графов в математике способствовали труды Эйлера.
Где мы встречаемся с графами? Наверное проще сказать где мы с ними не встречаемся. Вот лишь небольшой перечень, который сразу приходит на ум:

  • Модель локальной или глобальной сети
  • Блок-схема алгоритма
  • Принципиальная электрическая схема
  • Генеалогическое древо
  • Схема метрополитена
  • Модель связей в базе данных
  • Диаграммы Фейнмана
  • Ментальные карты

и очень многие другие вещи. Поднять всю теорию графов на этом уроке не представляется возможным, поэтому мы отправляем вас к списку (популярной) литературы на этой странице. Здесь же мы рассмотрим лишь те базовые понятия, которые нам пригодятся при составлении программ для работы с этой фундаментальной структурой.
Граф G — это упорядоченная пара G:=(V,E) , где V — это непустое множество вершин (или узлов), а E — множество пар вершин, называемых рёбрами. Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| — порядком, число рёбер |E| — размером графа.

Рис. 1. Неориентированный граф

Рис. 2. Дерево – это связный ацикличный граф

Глоссарий

Здесь мы сделали небольшую выборку терминов из теории графов (раздел дискретной математики), сама же дисциплина не обладает устоявшейся терминологией [2].

Базовая терминология

Рус En Описание
Вершина vortex Элемент графа
Узел node Тоже, что и вершина
Ребро edge Связь двух соседних вершин
Дуга arc Тоже, но в орграфе
Связь link Элемент графа (ребро или дуга)
Смежность adjacent О двух вершинах между которыми есть связь
Инцидентность incident on О ребре по отношению к вершине
Степень degree Число ребер инцидентных вершине
Основные понятия
    Маршрут в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром Цепью называется маршрут без повторяющихся рёбер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся рёбер) Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему Циклом называют цепь, в которой первая и последняя вершины совпадают (На рис. 1 ACD и ACDE – циклы) Длину пути (или цикла) называют число составляющих его рёбер Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются
Разновидности графов
    Ориентированный граф – (кратко орграф) — граф, рёбрам которого присвоено направление (рис. 4) Неориентированный граф – граф в котором пара вершин не является упорядоченной (рис. 3) Связный граф — граф в котором между любой парой вершин существует как минимум один путь Дерево — это связный ациклический граф, т.е. отсутствуют циклы и между парами вершин имеется только по одному пути (рис. 2). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода называются листьями. Взвешенный граф – граф в котором каждому ребру поставлено в соответствие некоторое число, называемое весом ребра

Методы представления графа

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

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

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n ) — это квадратная матрица A размера n , в которой значение элемента a[i][j] равно единице, если i -я и j -я вершины графа являются смежными, иначе значение равно нулю. Такая матрица называется бинарной. Для простого графа элементы главной диагонали равны 0 .
Матрица смежности подходит как для описания орграфа, так и для описания неориентированного графа. Для неориентированного графа значения элементов симметричны относительно главной диагонали. Симметрия матрицы смежности является её плюсом в плане экономии памяти, т. к. достаточно сохранить только половину матрицы (элемент a[i][j] == a[j][i] ).
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти будет тратиться впустую на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n 2 бит памяти, что может быть на порядок лучше списков смежности (см ниже).
В алгоритмах, работающих со взвешенными графами, элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или inf .

Матрицы смежности для орграфа и неориентированного графа

Рис. 3. Неориентированный граф

Для реализации матрицы смежности используется массив массивов: вектор векторов ( vector ), или вектор битсетов (если размер графа известен и изменяться не будет), или словарь, в котором ключ – номер вершины, а значение битсет (или vector , если на этапе компиляции размер битсета неизвестен). Если граф не предполагается расширять, то вектор целесообразно заменить на array .

Матрица инцидентности

Матрица инцидентности — форма представления графа, в которой указываются связи между инцидентными элементами графа (ребро – вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Отсюда, матрица не является квадратной. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждая дуга в соответствующем столбце имеет значение « −1 » в строке исходящей вершины x и « 1 » в строке входящей вершины y ; если связи между вершиной и ребром нет, то в соответствующая ячейка имеет значение « 0 ».

Матрицы инцидентности для орграфа и неориентированного графа

Рис. 5. Неор. граф

Применяется данный метод (из-за перерасхода памяти) крайне редко, в основном, для поиска циклов. Размер памяти пропорционален O(|V||E|) .

Список смежности

Список смежности — способ представления графа в виде коллекции списков вершин («список списков») – каждой вершине графа соответствует список смежных вершин. Например, граф на рис. 1 мы можем описать следующим списком смежности:

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

Сравнение с матрицей смежности

Операция Список смежности Матрица смежности
Проверка на наличие ребра (x,y) O(|V|+|E|) O(1)
Определение степени вершины O(1) O(|V|)
Использование памяти для разреженных графов O(|V|+|E|) O(|V| 2 )
Обход графа O(|V|+|E|) O(|V| 2 )

Реализация списков смежности может быть выполнена, аналогично матрице смежности за той лишь разницей, что список может иметь переменную дину. Например, с помощью вектора векторов или может быть использован словарь ( map ) в котором ключ – номер вершины, а значение – список смежных вершин, реализованный подходящим последовательным контейнером. Если граф является взвешенным, то информацию о весе ребра можно передавать как пару ( std::pair ) <номер_вершины, вес_ребра,_инцидентного_этой_вершине>. В качестве списка может выступать любой последовательный контейнер или словарь (для взвешенных графов).

Список ребер

Список ребер – это массив, в котором каждому ребру графа (элемент массива) соответствует список, в которой хранятся две вершины ( std::pair ), инцидентные ребру. Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными. Если необходимо хранить и вес, то элемент списка представляет собой кортеж ( std::tuple ) трех элементов (x, y, weight) . Размер занимаемой памяти: O(|E|) .

Поиск кратчайшего пути в графе

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

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

Алгоритм Флойда-Уоршелла разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.
Основная идея алгоритма. Пусть есть три вершины i , j , k и заданы расстояния между ними. Если выполняется неравенство

то целесообразно заменить путь i => j путем i => k => j . Такая замена выполняется систематически в процессе выполнения данного алгоритма и называется релаксацией. Такой же подход используется в алгоритме Дейкстры (см. ниже).
В программе используется вспомогательный массив, для определения кратчайших путей. Значения исходной матрицы заменяются значениями этих кратчайших путей. Иными словами, матрица смежности будет заменена матрицей кратчайших путей.

Рис. 7. Взвешенный ориентированный граф для иллюстрации в программе ext_17.1 алгоритма Флойда-Уоршелла

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет O(|V||E|log⁡|V| , что лучше, чем O(|V| 3 ) алгоритма Флойда — Уоршелла тогда, когда |E| 2 (условие плотности графа).

Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации.
Формальное определение алгоритма: дан взвешенный ориентированный граф G(V,E) без дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.
Идея алгоритма. Определяем массив D[] , в котором для каждой вершины v будем хранить текущую длину D[v] кратчайшего пути из s в v . Изначально D[s]=0 , а для всех остальных вершин эта длина равна бесконечности (некоторое значение, заведомо большее возможной длины пути):
Кроме того, для каждой вершины v будем хранить, помечена она ещё или нет, т.е. определим булевский массив U[] . Изначально все вершины не помечены, т.е. элементы массива имеют начальное значением false .
Сам алгоритм Дейкстры состоит из n итераций (по количеству вершин). На очередной итерации выбирается вершина v с наименьшей величиной D[v] среди ещё не помеченных.
Выбранная, таким образом, вершина v отмечается помеченной. Далее, на текущей итерации, из вершины v производятся релаксации: просматриваются все рёбра (v,to) , исходящие из вершины v , и для каждой такой вершины to алгоритм пытается улучшить значение D[to] . Пусть длина текущего ребра равна len , тогда в виде кода релаксация выглядит как:

В конце концов, после n итераций, все вершины графа станут помеченными, и алгоритм завершит свою работу.
Стоит заметить, что, если не все вершины графа достижимы из вершины s , то значения D[v] для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.

Рис. 8. Взвешенный граф для иллюстрации работы в программе ext_17.2 алгоритма Дейкстры

Обход графа в ширину

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли (1961 г.) независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах. Алгоритм обхода графа в ширину находит путь кратчайшей длины в невзвешенном графе, т. е. путь, содержащий наименьшее число рёбер. Граф может быть как ориентированным, так и неориентированным. Список смежности идеально подходит для работы с алгоритмом BFS. Временная сложность алгоритма O(n+m) , где n — число вершин, m — число рёбер.
Работу алгоритма можно представить как распространение круга пламени от источника возгорания. Пусть источником возгорания будет вершина s. Далее, на каждом следующем шаге, огонь перекидывается с каждой уже горящей вершины на всех её соседей. За одну итерацию алгоритма происходит расширение «кольца огня» в ширину на единицу (отсюда и название алгоритма).
Для реализации алгоритма используется структура данных очередь. Идея алгоритма. Создадим очередь q , в которую будут помещаться горящие вершины, а также определим булевский массив used[] , в котором для каждой вершины будем отмечать, горит она уже или нет, иными словами, была ли она посещена.
Изначально в очередь помещается только вершина s , и used[s] = true , а для всех остальных вершин used[] = false . Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все смежные с ней вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди. В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из s вершины, причём до каждой дойдёт кратчайшим путём.
Для подсчета длины кратчайших путей необходимо определить массив длин путей D[] , а для определения кратчайшего пути из одной вершины в другую — массив «предков» P[] , в котором для каждой вершины сохранять номер вершины, из которой мы попали в эту вершину.

Рис. 9. Неориентированный граф для иллюстрации работы в программе ext_17.3 алгоритма BFS

Обход графа в глубину

Поиск в глубину (англ. Depth-first search, DFS) является наиболее важным алгоритмом, который применяется для решения многих трудных задач обхода графов: проверки связности, поиска цикла и компонент сильной связности, для топологической сортировки. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Сложность алгоритма O(N+M) .
Для реализации алгоритма используется структура данных стек. Идея алгоритма. Поиск начинается с некоторой фиксированной вершины s . Далее рассматривается вершина v смежная с s . Она выбирается и отмечается как посещенная. Остальные смежные вершины (если они есть и они не посещены) отправляются в стек и ожидают следующего захода в родительскую вершину. Далее берется вершина q смежная с v . Действия повторяются. Так процесс будет продвигаться вглубь графа пока не достигнет вершины u такой, что не окажется вершин смежных с ней и не посещенных ранее. Если такая вершина получена, то осуществляется возвращение к вершине, которая была ранее (до неё) и там производится определение доступной вершины. В том случае, когда мы вернулись в вершину s , а все смежные вершины с ней уже посещены то алгоритм завершает свою работу.

Рис. 10. Граф для иллюстрации работы в программе ext_17.4 алгоритма DFS

Заключение

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

  • Поиск компонент связности
  • Нахождение кратчайшего цикла
  • Нахождение кратчайшего чётного пути
  • Поиск наименьшего общего предка
  • Поиск мостов

и мн. др. Разумеется, приведенными методами не исчерпывается все разнообразие методов работы с графами [3]. Разбор и усвоение некоторых важных алгоритмов вполне по силам учащимся старших классов. И дело здесь не только в подготовке к олимпиадам. Разбирая сложные задачи ученик учится программировать, оттачивает важный навык — составление эффективных алгоритмов.
При составлении программ этого урока использовались описания и реализации алгоритмов (язык программирования C++) на замечательном сайте MAXimal с которым мы рекомендуем вам обязательно познакомиться. Здесь представлено 145 алгоритмов, среди которых очень много алгоритмов на графах. Все материалы этого сайта распространяются под свободной лицензией. Также есть возможность скачать все алгоритмы одним файлом (pdf). Расширить ваш кругозор и познакомить с иными способами решения задач (в том числе и тех, которые мы рассмотрели на этом уроке) помогут источники перечисленные ниже.

Как сделать поиск кратчайшего пути на графе по массиву данных?

Есть неориентированный граф:

Можно ли (не важно каким методом) найти кратчайшие пути х1 -> х5 на графе используя массив данных ? Где x1..x2 значения из таблицы:

А в ответе получить таблицу путей:

  • Вопрос задан 02 апр.
  • 247 просмотров

Блин, народ, вы че, уже Google пользоваться разучились или попросту лень*?
Первая-же ссылка дает богатейшую пищу для мозгов:
https://habr.com/ru/post/119158/
А если чуть-чуть напрячь мозг и прочитать то, что написанопо следующим трем-четырем ссылкам, то можно уже будет из себя представлять крутого специалиста.
Если надо «просто загрузить массив и получить ответ«, то таких возможностей довольно много, вот например, один из них:
https://github.com/pmatiello/python-graph

А вообще, алгоритм поиска кратчайшего пути в графе изучается на любой специальности, хоть немного связанной с ИТ.

Судя по нарисованному графу, тут есть два варианта пути:
1. х1-х2-х5
2. х1-х3-х4-х5
Из этих двух нужно выбрать меньший.

Ребро х2-х3 нужно исключить, т.к. в треугольнике х1-х2-х3 всегда выгоднее выбирать одну из сторон х1-х3 или
х1-х2, чем две стороны (х1-х2 + х2-х3 или х1-х3 + х3-х2).

Зная это, простым сложением по вашей таблице легко найти ответ.

Задача определения кратчайшего пути

Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.

> ПРИМЕР 1.8. Узел 7 (рис 1.9) — склад, остальные узлы — строительные площадки компании. Показатели на дугах — расстояния в километрах.

Надо найти кратчайшие расстояния от склада до каждой строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки 1? Проходит ли кратчайший путь от склада к строительной площадке 1 через строительную площадку 2? Какова длина кратчайшего пути от склада до строительной площадки 2? Проходит ли кратчайший путь от склада к строительной площадке 2 через строительную площадку 4?

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

Итак, узлу 7 приписываем метку (О, S) (рис. 1.10), где 0 — это расстояние от узла 7, S- обозначение стартового узла.

Узел 7 связан с узлами 2, 4, 6. Длины соответствующих ребер — 17, 5, 6. Поэтому узлам 2, 4, 6 присваиваем временные метки — [17, 7], [5, 7], [6, 7] соответственно (рис. 1.11, первое число — длина пути от узла 7 до данного узла, а второе — предшествующий узел).

После выполнения этой операции можно сделать два следующих шага:

  • 1) найти участок (участки) минимальной длины и соответствующую временную метку (метки) сделать постоянной;
  • 2) узел (узлы), которому соответствует появившаяся постоянная метка, становится новым стартом.

После выполнения этой операции временная метка с наименьшим расстоянием до узла 7 становится постоянной. Это метка (5, 7) узла 4 (см. рис. 1.11). Поэтому следующий шаг мы начнем с узла 4.

Узел 4 непосредственно связан с узлами 2 и 5 без постоянных меток. Длина ребра 4-5 равна 4, метка узла 4 — (5, 7), временная метка узла 5 равна [5 + 4, 4] = [9,4] (рис. 1.12). Длина ребра 4-2 равна 6, метка узла 4 — (5,7), временная метка узла 2 равна

[5 + 6, 4] = [11, 4]. Таким образом, мы нашли путь от узла 7 до узла 2 длины 11.

Узел 2 ранее был помечен меткой [17, 7] (путь длины 17), но 11

Поиск кратчайшего пути

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

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

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

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

Многие олимпиадные задачи сводятся к поиску кратчайших путей. Обычно рассматривается следующая задача: дан граф, у которого веса ребер – неотрицательные числа, требуется найти кратчайший путь между парой вершин. Она решается с помощью алгоритма Дейкстры . Если граф может содержать ребра отрицательного веса, то применяется алгоритм Форда-Беллмана . Он так же позволяет определить, существует ли в графе отрицательный цикл. Если требуется найти кратчайшие пути между всеми парами вершин, то применяется алгоритм Флойда-Уоршелла .

Алгоритмы

В данном разделе будем полагать что если расстояние между (u, v) = INF (бесконечность), то в графе нет пути между (u, v). Значение константы INF должно быть достаточно большим, но желательно выбрать ее так, что, например, выражение INF + INF не вызвало бы переполнения.

Матрица смежности будет иметь следующий вид: a_uv = 0, если u = v, иначе длине ребра (u, v), если оно есть, иначе INF.

Алгоритм Дейкстры

Алгоритм Дейкстры позволяет найти кратчайшие пути от данной вершины до всех остальных вершин в графе. Алгоритм состоит из следующих шагов:

  1. Положить для всех вершин (кроме исходной) расстояние dist(v) = INF, для исходной dist(start) = 0.
  2. Выбрать непомеченную вершину v, с минимальным расстоянием. Если такой вершины нет, то завершить работу.
  3. Пометить v.
  4. Для всех непомеченных вершин, смежных с v, попытаться улучшить оценку расстояния.
  5. Вернуться к шагу 2.

Реализация на Java:

Заметим, что наш алгоритм нашел только стоимости кратчайших путей, а не сам путь между интересующими нас вершинами. На самом деле, этого зачастую достаточно, но если требуется найти путь, то алгоритм Дейкстры следует модифицировать. Введем еще одну характеристику – prev(v) = p – вершина из которой было улучшено расстояние до v на шаге 4 исходного алгоритма. Фактически, если объединить все кратчайшие пути из исходной вершины, то они образуют дерево. У любой вершины дерева, кроме корня есть ровно один предок. В конце работы алгоритма, prev(v) – и будет этим предком. Зная предков, можно легко восстановить и сам путь.

Пусть V – число вершин, E – число ребер графа. Заметим, что асимптотика нашего алгоритма O(V^2). Но для разряженных графов можно модифицировать алгоритм Дейкстры. Во первых, если отказаться от матрицы смежности, и перейти к спискам, то релаксация потребует только O(E) операций. Для ускорения получения ближайшей вершины необходимо применить специальные структуры данных (например, RMQ или кучу). Тогда получим асимптотику O(ElogV).

Реализация алгоритма Дейкстры с RMQ на Java:

Алгоритм Форда-Беллмана

Алгоритм Форда-Беллмана не очень быстр (O(VE)), но работает и на графах с отрицательными ребрами. Алгоритм достаточно прост: положить расстояния до исходной вершины – 0, для остальных INF, а затем V – 1 раз сделать всевозможные релаксации (их будет ровно E). Можно сделать оптимизацию: если на текущем шаге не удалось сделать ни одной релаксации – остановиться. Если после (V – 1)-ой итерации можно выполнить релаксацию, то в графе есть цикл отрицательного веса (его можно найти явно, если хранить предков).

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

Данный алгоритм находит кратайшие расстояния между всеми парами вершин за O(V^3). Описание алгоритма: фиксируем вершину k, затем перебираем всевозможные пары вершин (i, j) и если a_ij > a_ik + a_kj, то делаем a_ij = a_ik + a_kj.

Поэлементный поиск кратчайшего пути в пространстве

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

Аннотация
В данной статье рассматривается алгоритм поиска кратчайшего пути между двумя элементами в пространстве.

Актуальность. Задача поиска кратчайшего пути появилась довольно давно и включает довольно много алгоритмов (вариантов) их решения. Такие алгоритмы предполагают полный перебор всех возможных вариантов передвижения. Как правило, данные алгоритмы имеют широкое применение в игровых программах, когда необходимо найти и проложить кратчайший маршрут по игровому полю с учетом всех возможных препятствий. Актуальность данного алгоритма заключается в том, что мы заведомо узнаем кратчайший путь еще до начала маршрута. Это один из так называемых алгоритмов планирования. В достоинства данного алгоритма также входит то, что решение благодаря описываемому методу не всегда может быть единственным, но всегда будет однозначным.

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

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

Решение задачи и результаты исследований. Рассмотрим применение данного алгоритма для двумерной карты (двумерного массива), в которой для перехода от клетки к клетке существует четыре возможные варианта передвижения (вверх, вниз, влево и вправо). Пусть условно элемент массива «-1» будет преграда, через которую пройти нельзя, «1» – точка начала пути, «0» клетка через которую возможно передвижение, а «-2» будет пункт назначения. Понятно, что элементы «1» и «-2» должны встречаться единожды, иначе может произойти сбой алгоритма. Допустим, что для поиска кратчайшего пути нам была дана такая исходная карта:

Решением будет направление в какую из четырех сторон нужно предпринять движение (влево, вниз, вверх или вправо) из пункта «1» чтобы добраться пункта «-2», либо наглядно проложенный маршрут кратчайшего пути.
Визуально мы без труда его можем проложить:

Итого потратив на передвижение 2 клетки.
А теперь приступим к программированию самого алгоритма, который условно можно поделить на два основных этапа. Первый этап – этап подготовки матрицы так называемое планирование, когда оценивается количество ходов или тяжесть достижения каждой клетки от дальности первоначальной. Начинать возможный маршрут будем с координаты начала пути или значения «1». Когда мы передвинулись в соседнюю клетку с пометкой «0» (возможно перемещение в элементы только с этой пометкой), мы суммируем количество ходов, потраченное на перемещение к предыдущей клетке на единицу, а результат суммирования записываем в ту ячейку, в которую было совершено передвижение, т. е. с пометкой «0». За первый проход этапа планирования мы рассматриваем все возможные ситуации передвижения дальностью в 1 клетку от значения с координатами «1» первоначальной. То есть, таким образом, мы передвигаемся в соседние клетки, замеряя при этом «потраченные силы», записывая количество потраченных на них ходов. Итого после первого прохода мы получим следующий массив:

Если бы было возможно передвижение и по диагоналям мы получили бы такой массив:

Появилась третья «двойка» в которую мы никак не смогли бы попасть за один ход, передвигаясь в одно из четырех направлений.
Второй проход мы совершаем уже из клеток со значениями «2» в клетки значениями «0», которые иначе можно назвать «не пройденными». Словом так мы будем повторять до тех пор, пока ни останется, ни одной «не пройденной» клетки. Результат второго прохода:

После того как последняя «не пройденная» клетка будет заполнена количеством потраченных до нее ходов, получим такую матрицу:

На этом этап планирования заканчивается. Второй этап – прокладывание кратчайшего пути. Теперь мы будем двигаться от точки «-2» к точке «1» по наименьшему маршруту. Выбираем наименьший ближайший элемент больший нуля пункта назначения или «-2». Это будет элемент «3». То есть, чтобы добраться от пункта «1» к пункту «-2» понадобится ровно 3 хода. Далее рекурсивно двигаемся от «тройки» по наименьшим элементам к «1», предпоследнее направление передвижения даст сторону, в которую нужно двигаться, чтобы достичь цели (или пункта «-2»). Если после этапа подготовки матрицы соседние элементы пункта «-2» равны «0», то условия такой матрицы фиктивны, или попросту маршрут от начальной точки к пункту назначения невозможен. Пример такой матрицы:

А так будет выглядеть эта матрица после этапа планирования:

Понятно, что из-за препятствий достижение пункта «-2» не является возможным и точки «0» за «стенкой» остаются недостигнутыми. В таком случае работу алгоритма следует немедленно прекратить и проинформировать пользователя, что маршрут невозможен.
Совершенно необязательно использовать данный алгоритм именно под прямоугольную карту, иными словами границы которой очерчивают прямоугольник.
Края исходной карты под любую другую задачу могут выглядеть примерно вот так:

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

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Занятие 5. Решение задач ДП: Задача поиска кратчайшего пути (о поиске минимального расстояния)

Постановка задачи

Представим граф, представляющий собой воображаемую карту дорог, вершинами которого являются точки пересечения дорог или перекрестки (A11, A21, A31, A12, A22, A31, A13, A23…), см. рис. 5.1.

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

Рис. 5.1. Граф для задачи поиска кратчайшего пути

Итак, наша цель:

  1. определить путь минимальной длины;
  2. определить минимальное расстояние от дома до работы.

Введем условные дополнения:

  • ехать можно только в одну сторону — слева направо (например, из точки A21 можно двигаться только в точки A31 и A32)
  • расстояние между точками или перекрестками укажем в таблицах:
A11 A12 A13
Дом 1 2 3
A21 A22 A23
A11 2 1 1
A12 1 2 1
A13 2 3 2
A31 A32
A21 3 2
A22 3 3
A23 1 3
Работа
A31 4
A32 3

Как решить задачу без использования методов ДП?

Наивное решение

Наивным решением может быть метод перебора.

Граф имеет структуру — порядок слева направо.

  • взять 1-й путь и найти его длину d1
  • взять 2-й путь и найти его длину d2
  • взять k -й путь и найти его длину dk

После этого определить минимальный путь посредством процедуры argmin (di) , i=1. k

Т.е. решить такую задачу можно перебором.

Минус:
Посчитаем количество путей (из каждой вершины) — получим 18 путей.
Это не так мало, задача ведь простая.

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

Такие алгоритмы считаются не эффективными.

Другой вариант:
Можно воспользоваться так называемыми алгоритмами на графах, например, алгоритмом Дейкстра. О них поговорим на другой лекции.

Использование методов динамического программирования

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

Двигаясь от точки, обозначающей работу, разобьем граф на количество уровней перекрестков (рис. 5.2):

Рис. 5.2. Количество уровней перекрестков, которые надо пересечь, доехав до работы

Получилось 4 уровня перекрестков от Дома до Работы.

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

Предположим, что мы находимся на последнем уровне перекрестков от Работы.
На последнем уровне перекрестков минимальная длина пути из каждого перекрестка до работы известна (из таблицы) — это 4 и 3.

Зная минимальную длину пути из этого уровня перекрестков до Работы, можно ли найти минимальную дину пути из следующего уровня (A21, A22, A23) до Работы? — да можно. Например, из точки А21 нужно посмотреть всего два варианта: А21 -> A31 и A21 -> A32 . Затем выбрать минимальный из них, воспользовавшись процедурой argmin .

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

И так и продолжим, пока не найдем минимальную длину пути от Дома до Работы.

Словесный алгоритм мы разработали. Теперь приступим к решению.

FAij — минимальная длина пути из перекрестка Aij до работы.
Запишем формулу. Начнем с последнего уровня перекрестков, двигаясь влево.

F3,j (j)=1,2 F3,1 — минимальная длина пути из перекрестка A31 до Работы = 4
F3,2 — минимальная длина пути из перекрестка A32 до Работы = 3

F3,1 = 4
F3,2 = 3

F2,2 — это второй уровень, состоящий из перекрестков А21, А22, А23

Рассмотрим перекресток А22, из которого есть два пути:

    А22 argmin : 6 F2,2 = min[A22 -> A31 -> Работа; A22 -> A32 -> Работа] = min[3 + 4; 3 + 3] = 6 (А3,2)

Рассчитываем следующую ветвь второго уровня:

F2,1 = min[A21 -> A31 -> Работа; A21 -> A32 -> Работа] = min(3 + 4; 2 + 3) = 5 (А32)

Рассчитываем последнюю оставшуюся ветвь второго уровня:

Рассматриваем третий уровень перекрестков:

F1,1 (перекресток A11) = min[A11 -> A21 -> F2,1;A11 -> A22 -> F2,2;A11 -> A23 -> F2,3] = min[2 + 5;1 + 6;1 + 5] = 6 (A23) (А31)

F1,2 (перекресток A12) = min[1 + 5;2 + 6;1 + 5] = 6 (A23) (А21), можно взять любой минмимум из двух

F1,3 (перекресток A13)= min[2 + 5;3 + 6;2 + 5] = 7 (A23) (А21), можно взять любой минмимум из двух

F3 F2 F1
1 4 5 (A32) 6 (A23)
2 3 6 (A32) 5 (A21)
5 (A31) 7 (A21)

Осталось найти цель — из Дома:

FДом = min[1 -> A11 -> F11; 2 -> A12 -> F12; 3 -> A13 -> F13] = min[1 + 6;2 + 6;3 + 7] = 7 (A11)

Результат:

Длина минимального пути из Дома до Работы = 7
Восстановим минимальный путь: A11 -> A23 -> A31 — > Работа

Сложность решения: решая задачу с перебором, приходилось умножать ( 3 * 3 * 2 ), а в данной задаче нам необходимо складывать. Т.е. мы получаем вместо экспоненциальной функции эффективное полеомиальное решения.

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

Илон Маск рекомендует:  Атрибут list в HTML
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL