Читайте также:
|
Графы сети PERT и CPM бесконтурные.
Задача: найти самый длинный путь из источника (начало проекта), до конечной вершины (окончание проекта).
Такой путь называется критическим путем. Длина пути определяет время, необходимое для реализации всего проекта. Очевидно, что задача сводится к задаче о кратчайшем пути, если измененить знак каждого веса a(u, v) на обратный.
Существует несколько способов нахождения критического путя. Например, алгоритм Флойда (
) и алгоритм Форда–Беллмана 
.
40. Алгоритм Флойда — кратчайшее расстояние между всеми парами вершин. Обоснование. Сложность алгоритма. Транзитивное замыкание. Алгоритм Уоршала — нахождение транзитивного замыкания. Обоснование алгоритма Уоршала и его временная сложность.
Определить расстояния между всеми парами вершин можно, используя n раз 1 из рассм. методов нахождения расстояний от фиксир. вершины. В общем случае — алгоритм Форда–Беллмана со сложностью 
.
Однако, у алгоритма Флойда сложность 
.
Рассмотрим орграф G = <V, E>, где V = {v1,..., vn}, и предположим, что A = [aij] есть матрица весов (aij = a(vi, vj)). Обозначив через dij(m) длину кратчайшего пути из vi в vj, содержащего не более m дуг, получаем следующие очевидные уравнения:
; 
.
Дата добавления: 2015-11-16; просмотров: 69 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл относится к NP-классу. | | | Обоснование алгоритма Флойда. |