Задача 2: Задача о нахождении дерева кратчайших расстояний – нахождение кратчайшего пути из одной вершины в любую другую.
Пусть дан ориентированный связный граф со взвешенными ребрами. Вес ребра (xi,xj) обозначим cij.
Требуется найти в заданном графе путь, соединяющий две заданные вершины и доставляющий минимум или максимум суммарного веса входящих в него рёбер. Чаще всего эта функция трактуется как длина пути, и задача называется задачей о кратчайших путях.
Для решения этой задачи применяется алгоритм Дейкстры (Голландия, 1930-2002), реализующий принцип динамического программирования: сведение данной задачи к аналогичной, имеющей меньшую размерность так, чтобы её решение являлось частью решения большей задачи.
Суть алгоритма: начиная с исходной вершины (вес = 0), добавлять к пути по одной вершины, определяя её вес (метку) как расстояние до неё от исходной вершины через уже добавленные, возможно, меняя их вес.
После обработки всех вершин путь строится от конечной вершины по рёбрам, дающим соответствующий вес.
Описание алгоритма Дейкстры (минимальный путь):
Шаг 0. Устанавливаем для исходной вершины x1 постоянный вес w1=0. Всем остальным вершинам присваивается временный вес ∞.
Шаг 1. Вершина, имеющая меньший вес называется «ближайшей». Среди дуг, исходящих из ближайшей вершины выбираем дугу (xi,xj), имеющую меньший вес. Новый вес конечной её вершины xj вычисляем как минимум из имеющегося её веса wj и суммы wi+ ci,j. Повторяем эту операцию для остальных дуг ближайшей вершины.
Шаг 2. Когда все дуги ближайшей вершины проверены, текущий вес её становится постоянным и она (и исходящие из неё дуги) вычёркиваются из рассмотрения. Если остались невычеркнутые вершины, переходим к шагу 1.
Шаг 3. От конечной вершины по очереди строится обратный путь к исходной вершине против направления дуг. От текущей вершины выбирается та предшествующая, вес которой меньше веса данной вершины на вес соединяющей их дуги. В итоге путь придёт в исходную вершину x1 с весом w1=0.
Пример: Найти минимальный путь из вершины 1 в вершину 5.
Все вершины рассмотрены. Фактически найдены кратчайшие расстояния от вершины 1 до всех вершин графа.
Найдём путь до вершины 5. Её вес 20.
Предыдущая вершина 6. Её вес 11=20-9.
Перед ней вершина 3. Её вес 9=11-2.
Перед ней вершина 1. Её вес 0=9-9.
Это исходная вершина. Задача решена.
Ответ: кратчайший путь 1 – 3 – 6 – 5. Длина пути 20.
Алгоритм Дейкстры
(в случае неотрицательных весов.)
Дано: непyстой взвешенный гpаф G=(V,E) с неотрицательными весами дуг. Требуется найти кpатчайший пyть от s к t (s≠t).
Для данного взвешенного графа алгоритм дает кратчайшее расстояние от вершины V1 к вершине Vn.
Каждой вершине поставим в соответствие упорядоченную пару (∞,0). Первая координата вершины Vi(m,vr) будет означать присвоенное расстояние от вершины V1 к вершине Vi, а вторая координата — предыдущую вершину пути от V1 к Vi.
1) Начать в вершине V1(∞,0), заменить ее на V1(0,0) и сделать постоянной. Остальные вершины на этот момент оставить временными.
2) Когда вершина Vk (m,vr) станет постоянной, для каждой вершины Vj, смежной к Vk, прибавить величину m к расстоянию от вершины Vk к вершине Vj. Если это значение меньше, чем текущее расстояние, присвоенное вершине Vj, заменить текущее расстояние этой суммой и заменить вторую координату на Vk.
3) Найти минимум из расстояний, приписанных временным вершинам. Первую из вершин с таким расстоянием делаем постоянной.
4) Если Vn — не постоянная вершина, то возвращаемся к пункту 2).
5) Если Vn — постоянная вершина, то расстояние, присвоенное вершине Vn является кратчайшим расстоянием от V1 к Vn.
6) Для нахождения пути начать в вершине Vn найти предшествующую ей вершину пути (вторая координата). Для каждой вершины пути Vj находить предшествующую ей вершину пути, пока не будет достигнута вершина V1. Перестановка вершин в обратном порядке даст кратчайший путь.
ПРИМЕР. Пусть взвешенный граф, в котором отыскивается кратчайшее расстояние от вершины А к вершине F.
Поставив в соответствие каждой вершине упорядоченную пару (∞,0), рассматриваемый граф приводим к виду.
Приступим к построению путей от вершины А к другим вершинам.
Первая компонента упорядоченной пары покажет длину кратчайшего пути к вершине в момент достижения, а вторая — укажет на предыдущую вершину кратчайшего пути. Первая компонента будет содержать ∞, а вторая — 0 до тех пор, пока путь не найден.
Шаг1. Вершина, которая стала постоянной, будет выделена жирным шрифтом. Выполнив шаг 1 алгоритма, получаем граф
Шаг 2. Поскольку вершины В и С — смежные с вершиной А, выполняем шаг 2 и упорядоченной паре для вершины В присваиваем значение B(5, А), а упорядоченной паре для вершины С присваиваем значение C(6,А).
Шаг 3. Выполнив шаг 3, выбираем наименьшее из временных присвоенных значений. В данном случае это расстояние до вершины А, равное 5, и вершину В(5, А) делаем постоянной. Таким образом, получаем.
Возвращаясь к шагу 2, рассмотрим временные вершины С, D, Е и F, смежные с вершиной В. В каждом случае прибавляем расстояние от вершины А к вершине В к расстоянию от вершины В к данным вершинам.
Таким образом, для вершины С это будет 5 + 3 = 8. Для вершины D имеем 5 + 7 = 12. Для вершины Е имеем 5 + 2 = 7. Для вершины F получаем 5 + 10 = 15.
Поскольку новое расстояние до вершины С не меньше, чем уже присвоенное, упорядоченную пару С(6,А) оставляем без изменения. Новые расстояния до вершин Д Е и F меньше уже присвоенных, поэтому им задаем значения, которые получены для пути из вершины В, т.е. меняем их на D(12, В), Е(7,В) и F(15,В).
Выполнив шаг 3, находим наименьшее из расстояний, присвоенных временным вершинам, поэтому берем min = 6, и поскольку вершина С имеет это расстояние, делаем вершину С(6, А) постоянной. Таким образом, получаем.
Теперь берем новую постоянную вершину С. Выполнение шага 2 не приводит к изменениям. Выполнив шаг 3, делаем вершину Е(7,В) постоянной. Получаем
Берем новую постоянную вершину Е и, используя шаг 2, меняем F(15, В) на F(11,E). Выполнив шаг 3, делаем вершину F(11,E) постоянной. Таким образом, получаем.
Вершина F стала постоянной, поэтому процесс завершен и 11 — это кратчайшее расстояние от вершины А к вершине F.
Если бы совокупность вершин, смежных с постоянной вершиной, была исчерпана до того, как мы достигли вершину F, то задача не имела бы решения, поскольку не было бы пути от вершины А к вершине F.
Для нахождения кратчайшего пути заметим, что вершине F предшествует вершина Е, вершине Е предшествует вершина В, а вершине В предшествует вершина А. Поэтому кратчайшим путем является ABEF.
Алгоритм Дейкстры не всегда находит правильное решение в случае произвольных весов ребер (дуг) графа.
алгоритм Дейкстры найдет маршрут s(s,t)t длины 1 между вершинами s и t, а не минимальный маршрут длины 2+(-2)=0, проходящий через третью вершину графа.
Задача 3: Построение матрицы кратчайших расстояний – нахождение кратчайших путей для любой пары вершин.
Пусть дан ориентированный связный граф со взвешенными ребрами. Вес ребра (xi,xj) обозначим cij или C[i, j].
Требуется для каждой упорядоченной пары вершин v, w найти любой путь от вершины v в вершины w, длина которого минимальна среди всех возможных путей от v к w.
Пример прикладной задачи3:
Телефонная компания обслуживает пять удалённых друг от друга районов, которые связаны следующей сетью
Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между районами.
Для определенности положим, что вершины графа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу А размера nn, в которой вычисляются длины кратчайших путей.
Вначале A0[i, j] = C[i, j] для всех i j. Если дуга i j отсутствует, то C[i, j] = ∞. Каждый диагональный элемент матрицы А равен 0.
Над матрицей А выполняется n – 1 итераций. После k-й итерации A[i, j] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и j могут находиться только вершины, номера которых меньше или равны k.
На k-й итерации для вычисления матрицы А применяется следующая формула:
Для вычисления Ak[i, j] проводится сравнение величины Ak-1[i, j] (т.е. стоимость пути от вершины i к вершине j без участия вершины k или другой вершины с более высоким номером) с величиной Ak-1[i, k] + Ak-1[k, j] (стоимость пути от вершины i до вершины k плюс стоимость пути от вершины k до вершины j).
Если путь через вершину k дешевле, чем Ak-1[i, j], то величина Ak[i, j] изменяется.
Пример. Найти матрицу кратчайших расстояний для графа.
Источник
Задача №15. Графы. Поиск количества путей.
В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.
Рассмотрим простой и эффективный способ решения.
В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Решение:
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).
У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.
Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.
Индекс вершины Ж и будет ответом задачи.
Ответ: 11
Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими материалами из разделов нашего сайта.
Публикация обновлена: 05.08.2023
Источник