Курсовая работа: Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

Из самой структуры алгоритма очевидно, что для его функционирования необходимы:

1. Массив В-массив дуг-связностей в ячейках с номерами i, j которого будет находиться вес соответствующей дуги l _ij.

2. Массив М – массив изменивших свой вес вершин.

3. Массив Е – массив содержащий значения весов и состояний вершин.

4. Массив Р – массив содержащий выделенные дуги.

5. Ряд индексных переменных необходимых для перемещения по массивам В, Е, Р, а также содержащие индекс текущей вершины, и ряд буферных переменных необходимых для текущих арифметических и циклических операций (все индексы должны быть целочисленного типа).

4.4 Контрольный пример

Для подробного описания действия волнового алгоритма поиска длиннейшего пути воспользуемся графом задаваемым таблице связностей:

X1	X2	X3	X4	X5	X6
X1	1	4
X2	2	5
X3	2	4
X4	1	4
X5	2
X6

Таким образом, зная таблицу связностей можно построить граф для более наглядной иллюстрации примера:

Итак, на первом проходе волнового алгоритма выполняется пункт 1, т.е. устанавливаются значения весов всех вершин в нуль, и помещает в массив М индекс начальной вершины, математически это можно записать так:

Шаг №1:

П. 1:

На втором проходе, т. к. М<>0, выполняется пункт 2, из массива М забирается первый элемент, этот индекс присваивается индексной переменной i составляется множество исходов для вершины Х _i , а затем вычисляются веса смежных вершин:

Шаг №2:

П. 2:

Как видно из приведенных записей, в результате этого прохода две вершины: вторая и третья получили новые веса, и соответственно в массив М попали их индексы, так как до этого они в нем не содержались. (В дальнейшем для краткости изложения будут приводиться преимущественно математические записи работы алгоритма).

Шаг №3:

П. 2:

Следует отметить, что в результате этого прохода вершина Х ₃ не поменяла своего веса, так как уже имела максимально возможный.

Шаг №4:

П. 2:

Шаг №5:

П. 2: