Алгоритм Уоршелла. Построение матрицы транзитивного замыкания.
Допустим, у нас есть узел i и узел j. Тогда они связаны, если:
Или они соединены дугой;
Или существует путь из i в j через другие узлы.
Построение матрицы достижимости вершины j из вершины i. Исходной является матрица смежности A.
В алгоритме реализуется попытка добавить маршрут через узел k (1≤k≤n), если i и j на данный момент не являются концами цепи.
For k≔1 to n do
For i≔1 to n do
For j≔1 to n do
A[i,j]=A[i,j] or A[i,k] and A[k,j];
--I-- -------II-------
I – либо уже существует маршрут или дуга из i в j
II – либо существует маршрут или дуга из i в k и из k в j
Флойд распространил алгоритм Уоршелла и на взвешенные дуги, тем самым решил задачу нахождения кратчайшего расстояния между всеми парами вершин.
Алгоритм Флойда
Задачу нахождения кратчайшего расстояния между всеми парами вершин можно решить, используя алгоритм Дейкстры, если в качестве источника брать каждую из n вершин, т.е. n раз выполнять алгоритм Дейкстры.
Модификация Уоршелла для взвешенных дуг:
For k≔1 to n do
For i≔1 to n do
For j≔1 to n do
A[i,j]= min { A[i,j] , A[i,k]+A[k,j] };
Вот сам алгоритм (Сij – положительно определённая матрица(нет дуг отрицательной длины. Если дуги нет, то С[i,j]=∞)):
For i≔1 to |v| do
For j≔1 to |v| do
Begin
A[i,j]≔C[i,j]; //Перенос матрицы цен
P[i,j]≔0;
End;
For i≔1 to |v| do A[i,i]≔0; //Чтоб на петли не смотреть
For k≔1 to |v| do
For i≔1 to |v| do
For j≔1 to |v| do
If A[i,j] > A[i,k]+A[k,j] then
Begin
//Запоминаем новый маршрут
A[i,j]≔A[i,k]+A[k,j];
P[i,j]≔k;
End;
For i≔1 to |v| For j≔1 to |v| do begin
ВЫВОД Длина пути из i в j равна A[i,j]
По маршруту i, Path(i,j), j.
После k-той итерации элемент A[i,j] содержит кратчайшее расстояние из узла i в узел j, проложенное через узлы с номерами от 1 до k включительно. Для хранения маршрута, длина которого равна Aij, используется массив P.
Procedure Path(v,w:integer)
Var k:integer;
Begin
K≔P[v,w];
If k=0 then return;
Path(v,k);//рекурсивный поиск маршрута от i до k
Write(k);
Path(k,w);//рекурсивный поиск маршрута от k до w
End;
Центр орграфа
Центром графа G называется вершина с минимальным эксцентриситетом.
Эксцентриситет, или максимальное удаление вершины v есть максимальное удаление вершины w на множестве минимальных длин путей от w к v
Радиус графа – это максимальное удаление вершины (среди минимальных длин) от центра графа.
Диаметр графа – максимальное расстояние (среди минимальных длин) между вершинами графа.
Все эти задачи решаются при помощи алгоритма Флойда в матричном виде.
Например, для нахождения центра надо:
Используя алгоритм Флойда, построить матрицу кратчайших попарных расстояний.
Обходы графов
Обход графа - это процедура, представляющая собой эффективный метод систематического перебора вершин, используя существующие дуги графа. Существует 2 метода обходов графа:
Обход в глубину, или поиск в глубину (depth-first-search, DPS).
Обход в ширину, или поиск в ширину (breadth-first-search, BFS).
VAR w:integer;
PROCEDURE DFS(v:integer)
VAR i:integer;
BEGIN
FOR w:=1 to |v| do
//Если есть дуга и вершина куда ведёт она не посещена
IF A[v,w] and (mark[w]=unvisited) then
BEGIN
mark[w]=visited
DFS(w);
END;
END;
BEGIN
FOR w:=1 to |v| do
IF mark[w]=invisited
THEN BEGIN
mark[v]=visited;
DFS(w);
END;
END.
Алгоритм поиска в глубину
Используется вспомогательный массив mark с булевскими значениями (true – посещено; false – не посещено). Его нужно проинициализировать falsaми.
На каждом шаге для текущей вершины выбирается смежная и непосещённая вершина в лексикографическом порядке. После этого вершина отмечается как посещённая и выполняется перебор всех исходящих дуг для новой вершины. Этап продолжается до тех пор, пока все смежные непосещённые узлы не будут просмотрены аналогичным образом.
Чтобы обеспечить обход недостижимых с вершины старта узлов, необходимо реализовать цикл в лексикографическом порядке по всем вершинам и начинать запуск DFS (пункта 2) на каждой непосещённой ранее вершины.
Замечание. Массив mark – глобальный, поэтому все изменения его значений на любом уровне рекурсивного вызова DFS доступны (видны) и на последующих вызовах рекурсии – в этом смысл использования глобальных структур при рекурсивных вызовах процедуры.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Курсовая работа – до 1 мая (на отличную оценку) [[реально до 29 апреля]]
Сортировка оценка f(n) O(f(n))
Теперь расширить функционал программы с помощью GetTickCount(); засечь время начала и время завершения сортировки, соответственно время работы – время окончания минус время начала.
В качестве результата работы алгоритма (скриншот) нужно получить T(N).
Затем посчитать с помощью глобальной переменной N_op количество элементарных инструкций.
Теоретическое время – N, T(N) и N_op
f(N), o(f(n)),
ОБЯЗАТЕЛЬНО МИНИМИЗИРОВАТЬ ВНЕШНИЕ ФАКТОРЫ – не просматривать видео, не запускать из-под отладчика и т.п.
Хохма
Поэтому выбираем
константу не c, а
.
Отчёт о курсовой работе должен содержать:
Титульный лист
Задание на курсовую работу
Исходник, на основе которого получено
Полные выкладки
(через суммирование по циклам)Таблица вида
#
N
T(N)
N_op(N)
F(n)
O(F(n)
C1
C2
C3
C4
1000
.
.
.
10000
Графики зависимостей
Чтобы график был близок к прямой-константе.
Скриншот, подтверждающий вид таблицы
Полный листинг программы.
Для определения того, в каком отношении находится посещаемый и посещённый элемент (предок-потомок) можно использовать глубинное число, равное номеру в момент посещения конкретного узла.
Тогда у предка глубинное число меньше. У потомка – больше.