Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Нахождение кратчайших путей между парами вершин

Прошитые БД | Применение деревьев. Представление сообщений кодами Хаффмана | Идеально сбалансированные бинарные деревья | Бинарные деревья поиска | Сбалансированные деревья поиска | Операции над деревьями | Вставка элемента в АВЛ-дерево | Основные определения ориентированных графов | Представление ориентированных графов | Операторы над ориентированными графами |


Читайте также:
  1. I Международный Nail-фестиваль
  2. I. Международные нормативно-правовые акты.
  3. I. Международные нормативно-правовые акты.
  4. I. О различии между чистым и эмпирическим познанием
  5. I. Подведомственность дел о разделе между супругами совместно нажитого имущества.
  6. I.I.4. Структурные сдвиги во всемирном хозяйстве и международном экономическом обмене. Новые и традиционные отрасли.
  7. II. Подсудность дел о разделе между супругами совместно нажитого имущества.

 

Пусть дан орграф G=(V, E) и необходимо определить кратчайшие пути между всеми парами вершин орграфа. Каждой дуге этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, w) любого пути от вершины v в вершины w, длина которого минимальна среди всех возможных путей от v к w.

Для решения поставленной задачи применим алгоритм Флойда. Для этого пронумерует вершины графа последовательно от 1 до n.

Алгоритм Флойда использует матрицу А размера в которой вычисляются длины кратчайших путей. Вначале А[i, j] = C[i, j] для всех i ≠ j. Если дуга отсутствует, то C[i, j]=∞. Каждый диагональный элемент матрицы А равен 0.

Над матрицей А выполняется n итераций. После к -ой итерации А[i, j] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим к,т.е. между концевыми вершинами пути из i в j могут находиться только вершины, номера которых меньше или равны к. На к -ой итерации для вычисления матрицы А применяется следующая формула:

Нижний индекс к обозначает значение матрицы А после к -ой итерации. Графическая интерпретация приведенной формулы показана на рис. 42.

 

 

Рис. 42 – Включение вершины к в путь от вершины i к вершине j

 

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

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

 

Рис. 43 – Помеченный орграф

 

Рис. 44 – Последовательные значения матрицы А

 

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

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


Дата добавления: 2015-07-16; просмотров: 159 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Нахождение кратчайшего пути на ориентированном графе| Транзитивное замыкание

mybiblioteka.su - 2015-2024 год. (0.005 сек.)