русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Вычисление весов кратчайших путей в восходящем порядке


Дата добавления: 2013-12-23; просмотров: 747; Нарушение авторских прав


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

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

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

Первый способ заключается в применении алгоритма Дейкстры, выбирая поочередно каждый узел орграфа в качестве источника. Пусть n=|V|. Временная сложность алгоритма Дейкстры O(n2). Применяя его в цикле для каждого из n узлов, получим временную сложность алгоритма O(n3).

Второй способ заключается в применении алгоритма, известного как алгоритм Флойда-Варшалла (Floyd-Warshall algorithm) или алгоритма Флойда. Временная сложность его в худшем случае также равна O(n3).

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

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

Предположим, что орграф состоит из узлов . Рассмотрим подмножество узлов для некоторого . Для произвольной пары узлов рассмотрим все пути из узла в узел , все промежуточные узлы которых выбраны из множества . Пусть среди этих путей — путь с минимальным весом (этот путь простой). В алгоритме Флойда используется взаимосвязь между путем р и кратчайшими путями из узла в узел , все промежуточные узлы которых принадлежат множеству . Эта взаимосвязь зависит от того, является ли узел k промежуточным на пути .

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



Рис.4.2.1.

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

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

Далее нижний индекс обозначает значение матрицы или P после -й итерации

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

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

Над матрицей выполняется итераций.

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

На-й итерации для вычисления матрицы применяется следующая формула:

 

Графическая интерпретация этой формулы показана на рис 4.2.2.

 

 

 

Рис. 4.2.2 Включение узла в путь от узла к узлу

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

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

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

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

Пример.


Рис. 4.2.3 Помеченный ориентированный граф

На рис. 4.2.3 показан помеченный орграф, а далее представлены значения матриц А и P после трех итераций.

 

 

A0   P0   A1   P1
     
     
     
                                     
A2   P2   A3   P3
     
     
     

 

Равенства и означают, что на -й итерации элементы матрицы , стоящие в -й строке и -м столбце, не изменяются.

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

 

 

 

 

 

 

 

 

 

По окончательным значениям матриц A3 и P3 восстановим кратчайшие пути и их стоимости.

От узла 1 до узла 2: , . Кратчайший путь , его стоимость .

От узла 1 до узла 3: . Кратчайший путь , его стоимость .

От узла 2 до узла 1: . Кратчайший путь , его стоимость .

От узла 2 до узла 3: , . Кратчайший путь , его стоимость .

От узла 3 до узла 1: , . Кратчайший путь , его стоимость .

 



<== предыдущая лекция | следующая лекция ==>
Лекция №5. Размеры | Транзитивное замыкание


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.