Словесное описание алгоритма и его работы

 

1. Все вершины графа получают веса V _i =0, номер вершины X _н заносится в массив М номеров вершин, изменивших вес. Остальные вершины X _i не попадают в массив М.

2. Если массив М пуст, выполняется п. 3, иначе выбирается с исключением из его очередная вершина X _i и пересчитываются веса вершин, принадлежащих исходу G (X _i) вершины X _i:

 

 

Если вес V _j изменяется, то номер j включается с приведением подобных в М. Снова выполняется п. 2.

3. Если вес , то делается вывод, что пути из вершины X _н к вершине X _k не существует, иначе выполняется процедура выделения дуг, двигаясь в обратном порядке проверяем выполняется ли условие X _i – X _j = l _ij, для входов  вершины X _i, если оно выполняется, то вершина X _j и дуга l _ij выделяются.

4. После выделения дуг строятся длиннейшие пути, длины которых равны V _k.

При построении длиннейших путей рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполнения циклов.

Структуры данных

 

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

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

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

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

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

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

 

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

 

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

 

	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:

 

Шаг №6:

 

П. 2:

 

Шаг №7:

 

П. 2:

 

Шаг №8:

 

П. 2: М=0, выполняется п. 3.

 

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

На этапе выполнения третьего пункта алгоритма критерием для выделения дуги, как и для алгоритма нахождения кратчайшего пути, является совпадение разности весов соответствующих вершин с весом самой дуги. Таким образом, начиная с вершины Х6 получим:

Шаг №9: Для выделенной вершины

 

П. 3:

, поэтому дуга  выделяется.

, и дуга выделяется, одновременно выделяются вершины  и .

 

Шаг №10: Для выделенной вершины

 

П. 3:

, поэтому дуга  не выделяется.

, и дуга выделяется, одновременно

выделяется вершина .

 

Шаг №11: Для выделенной вершины

 

П. 3:

, поэтому дуга  выделяется.

, и дуга выделяется, одновременно выделяется вершина , следует отметить, что вершина  не выделяется, так как уже выделена.

 

Шаг №12: Для выделенной вершины

 

П. 3:

, поэтому дуга  не выделяется.

, и дуга выделяется, одновременно выделяется вершина .

 

Шаг №13: Для выделенной вершины

 

П. 3:

, и дуга выделяется, следует отметить, что вершина  не выделяется, так как уже выделена.

 

Шаг №14: Для выделенной вершины

П. 3:

 

Так как в данную вершину не входит не оной дуги и больше нет отмеченных вершин, переходим к этапу составления длиннейшего пути.

Итак соединяя дуги по принципу: конечный индекс предыдущей – начальный последующий, получаем три длиннейших путей  длиной 10:

1.

2.

3.

 

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

Приведем табличный метод записи процесса:

 

 

 

Заключение

 

В данной работе разработаны алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему. Алгоритмы исполнены с нужной степенью детализации, необходимой для понимания их работы. Рассмотрены пути улучшения эффективности каждого алгоритма учитывая требования конкретной задачи.

Большое внимание уделено сравнению возможного использования нескольких структур данных, проведён анализ эффективности работы алгоритма в зависимости от используемой структуры.

Рассмотрена сложность каждого алгоритма, её зависимость от условий данной задачи, методы упрощения и облегчения понимания алгоритма.