2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе
Начальные понятия
Будем рассматривать ориентированные графы G = <V, E>, дугам которых приписаны веса. Это означает, что каждой дуге <U, V> ОE Поставлено в соответствие некоторое вещественное число A (U, V), называемое Весом данной дуги.
Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами S, T ОV. Длину такого кратчайшего пути мы будем обозначать D (S, T) и называть Расстоянием от S до T (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из S в T, то полагаем D (S, T) = г. Если каждый контур нашего графа имеет положительную длину, то Кратчайший путь будет всегда элементарным путем, т. е. в последовательности V1,..., VP не будет повторов.
С другой стороны, если в графе существует контур отрицательной длины, то расстояние между некоторыми парами вершин становится неопределенным, потому что, обходя этот контур достаточное число раз, мы можем показать путь между этими вершинами с длиной, меньшей произвольного вещественного числа. В таком случае, можно было бы говорить о длине кратчайшего элементарного пути, однако задача, поставленная таким образом, вероятно будет значительно более сложной, так как, в частности, она содержит в себе задачу существования гамильтонова пути.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, Длина Которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать Стоимости (или Времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги ?U, V? Равен Вероятности P(U, V) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса P(U, V) на
A (U, V) = - lg P(U, V).
Сначала рассмотрим Алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных S, T О V (S, t) существует вершина V, такая что
D (S, T) = D (S, V) + A (V, T).
Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из S в T.
Далее мы можем найти вершину U, для которой
D (S, v) = D (S, U) + A (U, V), и т. д.
Из положительности длины всех контуров легко следует, что созданная таким образом последовательность T, v, U, ... не сожержит повторений и оканчивается вершиной S.
Очевидно, что она определяет (при обращении очередности) кратчайший путь из S в T.
Таким образом, мы получаем следующий алгоритм:
Алгоритм нахождения кратчайшего пути
Данные: Расстояния D[V] от фиксированной вершины S До всех остальных вершин V О V, фиксированная вершина T, матрица весов ребер, A[U, V], U, V ОV.
Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из S в T.
Begin
CTEK := Ж ; CTEK Ь t; V:= T;
While v ¦ s do
Begin
U := вершина, для которой D[V] = D[U] + A[U, V];
CTEK Ь u;
V:= U
End
End.
Пусть <V, E> - ориентированный граф, | V| = N, | E| = M. Если выбор вершины U происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(N2). Если мы просматриваем только список ПРЕДШ[V], содержащий все вершины U, такие что U (r) v, то в этом случае сложность будет O(M).
Отметим, что в случае положительных весов ребер задача о кратчайшем пути в Неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {U, V}двумя дугами б U, VсИ бV, Uс, каждая с таким же весом, что и {U, V}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.
Далее будем всегда предполагать, что G = < V, E>Является ориентированным графом, |V| = N, |E| = M. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых "большинство" вершин изолированные.
Будем также предполагать, что веса дуг запоминаются в массиве A[U, V], U, V О V (A[U, V] содержит вес A (U, V)).
Кратчайшие пути от фиксированной вершины
Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами S и T опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[U, V], U, V--О V, вычисляются некоторые верхние ограничения D[V] на расстояния от S до всех вершин V ОV. Каждый раз, когда мы устанавливаем, что
D[U] + A[U, V] < D[V], оценку D[V] улучшаем: D[V] = D[U] + A[U, V].
Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно.
Легко можно показать, что значение каждой из переменных D[V] равно тогда D (S, V) - расстоянию от S до V.
Заметим, что для того чтобы определить расстояние от S до T, мы вычисляем здесь расстояния от S до всех вершин графа.
Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.
Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины U И V для проверки условия минимальности расстояния. Эта очередности, как будет показано ниже, очень сильно влияет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой Источником, его всегда будем обозначать через S, до всех остальных вершин графа.
Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л. Р. Форда и Р. Е. Беллмана.
Похожие статьи
-
1.2 Основные термины и теоремы теории графов - Определение кратчайшего пути в графе
1. Граф - Пара объектов G = ( X, Г ),где Х - конечное множество, а Г - конечное подмножество прямого произведения Х*Х. При этом Х называется множеством...
-
Теория Графов, 1.1 Историческая справка - Определение кратчайшего пути в графе
Граф дискретный программирование 1.1 Историческая справка ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический...
-
Введение - Определение кратчайшего пути в графе
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера...
-
Основные определения, термины и понятия - Визуализация графа цитирования
1. Граф - совокупность множества вершин и наборов пар вершин, называемых ребрами. 2. Ориентированный граф - граф в котором пары вершин в ребрах...
-
Задачи на графах, 2.1 Описание различных задач на графах - Определение кратчайшего пути в графе
2.1 Описание различных задач на графах Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех...
-
Силовые алгоритмы расположения вершин на плоскости - Визуализация графа цитирования
Классический подход к решению таких задач это использовать алгоритм из семейства силовых. Основная идея таких алгоритмов - это рассматривать графы как...
-
Визуализация кластерной структуры. Bubble Sets - Визуализация графа цитирования
Для визуализации кластерной структуры был выбран алгоритм Bubble Sets [18]. Это гибкий алгоритм, относящийся к оверлеям, основанным на областях...
-
Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования
На данный момент мы рассмотрели алгоритм для отрисовки некластеризованных графов и их улучшения. Теперь необходимо изучить подходы, которые используются...
-
Поиск кратчайшего пути в лабиринте на языке Си
Лабораторная работа № 3 Поиск кратчайшего пути в лабиринте на языке Си Формулировка задания Найти кратчайший путь в лабиринте от текущего положения до...
-
Автоматическое расположение вершин на плоскости - Визуализация графа цитирования
Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она...
-
Библиотека GridMD поддерживает три механизма определения действий, связываемых с узлами графа [8]. Узел графа может соответствовать исполнению стороннего...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Автоматическая расстановка вершин на плоскости Для автоматической расстановки вершин использовался алгоритм основанный на работах Eades [9],...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Постановка задачи - Визуализация графа цитирования
В качестве результата выпускной квалификационной работы требуется создать программу, позволяющую визуализировать граф цитирования публикаций, которые...
-
ФАЙЛОВАЯ СИСТЕМА. ПАПКИ И ФАЙЛЫ. ИМЯ, ТИП, ПУТЬ ДОСТУПА К ФАЙЛУ - Программное обеспечение компьютера
Файл -- это информация, хранящаяся на внешнем носителе и объединенная общим именем. Файлы имеют свои названия. Их называют именами файлов. На диске есть...
-
Реализация визуализации анимации алгоритма - Визуализация графа цитирования
При работе алгоритма расположения вершин графа необходимо анимировать изменения графа в режиме реального времени. Для этого используется специальная...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Перед написанием основных алгоритмов были разработаны модули-классы, отвечающие за геометрические примитивы. Так как визуализация производится в...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Визуализация кластерной структуры - Визуализация графа цитирования
Следующей задачей, после расстановки вершин на плоскости, должна быть решена задача визуализации кластерной структуры. В данном разделе мы рассмотрим...
-
Существующие решения - Визуализация графа цитирования
На данный момент не было найдено решений, которые полностью бы удовлетворяли всем требованиям, однако существуют те, которые реализуют их не все и/или не...
-
Улучшения классических силовых алгоритмов - Визуализация графа цитирования
Первым улучшением является добавление псевдо-гравитационной силы [11]. Эта сила притягивает все вершины к центру рабочей области. Обычно она линейна...
-
Заключение - Разработка программы для реализации редактора временных графов синхронизации
Результатом выполнения задания является реализованный редактор временных графов синхронизации (класс временных сетей Петри), соответствующий задачам,...
-
Обзор сетей передачи данных, Определение локальных сетей - Сеть абонентского доступа
Определение локальных сетей Способов и средств обмена информацией за последнее время предложено множество: от простейшего переноса файлов с помощью...
-
Введение - Визуализация графа цитирования
В данной работе рассматриваются методы автоматической и полуавтоматической визуализации графов цитирования на плоскости. Визуализация графов на плоскости...
-
Основные понятия и определения Прежде чем приступить к обсуждению вопросов оптимизации, введем ряд определений и рассмотрим основные понятия. Оптимизация...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Для оценки возможности выполнения проекта имеющимся в распоряжении разработчика штатным составом исполнителей, нужно рассчитать их среднее количество,...
-
Использование муравьиных алгоритмов для решения задачи поиска оптимального маршрута в графе Цель работы Изучить метод муравьиных колоний. Научиться...
-
20. Пользователь через UI инициирует создание определения 21. Приложение получает данные описывающие определение и изменяет свое состояние 22. Приложение...
-
Численные эксперименты были проведены для следующих целей: Подтверждение корректности алгоритмов. Подтверждение линейности временных затрат алгоритмов. В...
-
Определение требований - Программный продукт
Этот шаг является важнейшим среди всех шести этапов процесса разработки. Он влияет на все остальные этапы. Увы, это наименее изученный и наименее...
-
Файл - это однородная по своему назначению совокупность информации, хранящаяся на диске и имеющая имя. Файлы различаются по своим именам. Имя файла может...
-
Для решения сформулированной задачи, т. е, для нахождения оптимального варианта конструкции наиболее эффективным является метод динамического...
-
Пример выбора путей - Многопротокольная коммутация по меткам
В примере, показанном на риc. 10, ограничением является максимально допустимое значение коэффициента использования ресурсов, равное 0,65. В варианте 1...
-
Заключение - Визуализация графа цитирования
Визуализация мягко кластеризованных графов цитирования - актуальная и сложная задача, требующая многоуровневых и сложных подходов для решения. Но решение...
2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе