Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Алгоритм Флойда – это алгоритм поиска кратчайшего пути между любыми двумя вершинами графа.
Рассматриваемый алгоритм иногда называют алгоритмом Флойда-Уоршелла. Алгоритм Флойда-Уоршелла является алгоритмом на графах, который разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.
Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей.
Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя вершинами графа.
В алгоритме Флойда используется матрица A размером nxn, в которой вычисляются длины кратчайших путей. Элемент A[i,j] равен расстоянию от вершины i к вершине j, которое имеет конечное значение, если существует ребро (i,j), и равен бесконечности в противном случае.
Алгоритм Флойда
Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.
Шаг 0. Определяем начальную матрицу расстояния A0 и матрицу последовательности вершин S0. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.
Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1. Если выполняется неравенство , тогда выполняем следующие действия:
создаем матрицу Ak путем замены в матрице Ak-1 элемента A[i,j] на сумму A[i,k]+A[k,j] ;
создаем матрицу Sk путем замены в матрице Sk-1 элемента S[i,j] на k. Полагаем k = k + 1 и повторяем шаг k.
Таким образом, алгоритм Флойда делает n итераций, после i -й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до i -й. На каждой итерации перебираются все пары вершин и путь между ними сокращается при помощи i -й вершины (рис. 45.2).
(рис. 45.2) Демонстрация алгоритма Флойда
Заметим, что если граф неориентированный, то все матрицы, получаемые в результате преобразований симметричны и, следовательно, достаточно вычислять только элементы, расположенные выше главной диагонали.
Если граф представлен матрицей смежности, то время выполнения этого алгоритма имеет порядок O(), поскольку в нем присутствуют вложенные друг в друга три цикла.
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами.
P.S.(Lyudi nihrena ne nawla norm(( esli naidete pls isprav’te) Thanks
3. Определить для двудольного графа максимальное паросочетание
Двудольным графом называется граф, у которого множество вершин можно разбить на два непересекающихся подмножества так, что ребра соединяют вершины из разных подмножеств.
Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин).
Паросочетание называется максимальным для данного графа, если оно содержит наибольшее число ребер для всех возможных паросочетаний.
Венгерский алгоритм нахождения максимального паросочетания.
Дан двудольный граф. Все определения для графа справедливы.
Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер.
1. Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.
Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.
Вершины, которые соединены толстыми ребрами – насыщенные. Остальные – ненасыщенные.
Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются.
Тонкой чередующейся цепью называется чередующаяся цепь, соединяющая 2 ненасыщенные вершины (В ней тонких ребер на 1 больше, чем толстых).
1. Находим полное паросочетание.
2. Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.
3. Если же она существует, то проводим перекраску ребер.
4. Толстые ребра тонкой цепи делаем тонкими, а тонкие – толстыми.
5. Получаем новое паросочетание, т.е. из исходного паросочетания удаляем те толстые ребра, которые входили в тонкую цепь и вместо них добавляем тонкие ребра из этой цепи.
6. Переходим на шаг 2.
Количество ребер в новом паросочетании увеличится на 1.
Максимальное паросочетание (МПС) найдено.
Совершенное ПС – МПС обязательно.
Матрицы смежности двудольных графов.
A(M,N)
[V] = M
[W] = N
Aij = 1, если есть ребро ViWj
Если его нет, то Aij = 0.