3.2. Алгоритмы нахождения оптимального пути

Путь из начальной вершины к конечной вершине- последовательность дуг, начинающаяся в вершине, заканчивающаяся в вершине, и такая, что конец очередной дуги является началом следующей:

.

Элементарный путь – путь, в котором вершины не повторяются.

Простой путь – путь, в котором дуги не повторяются.

Маршрут - последовательность рёбер, составляющих, как и путь, цепочку.

Длина пути взвешенного графа определяется как сумма весов его дуг. Если граф не взвешен, то можно считать веса всех дуг равными 1.

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

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

Волновой алгоритм построения кратчайшего пути для взвешенного графа.

1. Вершина получает вес, её номер вводится в массивМ номеров вершин, изменивших вес. Остальные вершины получают веси их номера не попадают в массив M.

3

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

 x_i  V_j =min(V_j, V_i+ lij)). Если вес V_i уменьшается, то номер j включается с приведением подобных в М. Снова выполняется пункт 2.

3. Если вес V_k =, то делается вывод, что пути из вершины x_н к вершине x_к нет, иначе выполняется процедура выделения дуг, такая же, как в волновом алгоритме для невзвешенного графа, за исключением того, что разность весов вершин x_j и x_i должна быть равна , т. е. V_i--V_j=l_ij.

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

Обратите внимание на то, что алгоритм выполняется в 3 прохода. На 1-ом проходе (это п.2 словесного описания алгоритма – СОА) вычисляются и пересчитываются в зависимости от прохождения волны, исходящей от рассматриваемой вершины и доходящей до смежных с ней вершин, веса всех вершин, включая конечную (x_кон=x₆). На 2-м проходе (это п.3 СОА) выявляютя «претенденты» на кратчайший путь, т.е. дуги, которые могут составить этот путь (эти пути, поскольку их может оказаться несколько с одинаковым весом). На 3-м проходе из дуг-претендентов составляются конкретные кратчайшие пути.

На с.6 приведена таблица процесса решения для 1-го прохода алгоритма.

В п.3 СОА имеется ссылка на волновой алгоритм для невзвешенного графа (можно считать, что для такого графа веса всех дуг одинаковы и равны 1), с учётом которого процедура выделения дуг–претендентов формируется так.

Выделяем текущую вершину x_i, начиная с конечной, и записываем множество всех вершин, смежных с текущей: G^-1(x_i)={x_j,x_m…}; здесь номера вершин упорядочены по возрастанию. Затем последовательно для каждой вершины из множества G^-1(x_i) определяем вес дуги как разность весов вершин, текущей x_i и рассматриваемой x_j. Если v_i-v_j=l_ij, где l_ij- вес дуги, а v_i, v_j – веса вершин, вычисленные на первом проходе (окончательные значения!), то эта дуга является фрагментом одного из кратчайших путей. Далее x_j полагаем текущей вершиной и переходим на начало этой процедуры. Процедура заканчивается при достижении начальной вершины.

4

Несмежные вершины отмечены в таблице единицами. Далее решается задача построения одного кратчайшего покрытия (методом минимального столбца - максимальной строки). Вершины, принадлежащие каждому подмножеству, вошедшему в найденное кратчайшее покрытие, окрашивается одной краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остаётся, из остальных исключается. Для нашего примера получим два подмножества: Y₁,Y₂,Y₃, определяющие три краски 0,1,2 соответственно. как показано на рис. 3.13, если x₁ покрасить краской 0, то все смежные с ней вершины x₂, x₃, x₄, x₅ нельзя покрасить 0; x₂, x₄ - смежные, для них необходимы две разные краски (1 и 2), x₃, x₄ - аналогично. Таким образом, изображенная на примере раскраска - минимальна.