ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Нахождение кратчайших путей между парами вершин
Пусть дан орграф 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, количество дуг в орграфе, значительно меньше, чем , то рекомендуют применять алгоритм Дейкстры со списками смежности. Тогда время нахождения кратчайших путей имеет порядок что значительно луче алгоритма Флойда, хотя бы для больших разреженных графов. Лекция 14 План лекции: 1. Транзитивное замыкание. 2. Нахождение центра ориентированного графа. 3. Обход ориентированных графов. 4. Глубинный остовный лес.
Не нашли, что искали? Воспользуйтесь поиском:
|