23.05.2024 / Ациклические пути

Определения

Ориентированный граф без циклов называется ориентированным ациклическим графом.

Путь в графе - последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Ориентированный цикл. Без стрелок это просто цикл.

Постановка задачи

В задаче поиска кратчайших путей полагаются известными множества вершин и ребер ориентированного или неориентированного графа $G(V,E)$ ($V$ - множество вершин, $E$ - множество ребер), а также вес ребер, где значение веса выражается действительным числом.

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

• является ли граф ориентированным или неориентированным;

• является ли граф ациклическим или содержит циклы;

• принимают ли веса ребер только положительные значения или возможны и их отрицательные значения;

• принимают ли веса ребер только целочисленные значения;

• выражаются ли веса ребер малыми неотрицательными значениями.

Способы решения

1. Алгоритм Беллмана-Форда для общего случая, когда вес каждого из ребер может быть отрицательным, с трудоемкостью $O(V \times E)$, где дополнительно определяется наличие цикла с отрицательным весом.

2. Алгоритм поиска в ширину для случая ориентированных ациклических графов с трудоемкостью $O(V + E)$.

3. Алгоритм Дейкстры для произвольных графов с неотрицательными весами ребер, где трудоемкость определяется в зависимости от способа выборки помеченной вершины с минимальным весом, и при использовании пирамид Фибоначчи может достигать величины порядка $O(V \lg V + E)$.

Для вывода кратчайшего пути мы можем использовать следующий алгоритм:

1. Начинаем с конечной вершины (в данном случае, вершина 5), и для каждой вершины, с которой она связана, вычитаем вес соответствующего ребра из длины пути конечной вершины.

2. Например, для вершины 5 с длиной пути 20, связанной с вершинами 6 и 4, вычитаем вес ребра и получаем: для вершины 6 - 20-9=11 (совпадает), для вершины 4 - 20-6=14 (не совпадает).

3. Если полученное значение совпадает с длиной пути рассматриваемой вершины, то это означает, что из этой вершины был осуществлен переход в конечную вершину. Отмечаем эту вершину как часть кратчайшего пути.

4. Затем определяем ребро, через которое мы попали в найденную вершину, и продолжаем этот процесс, пока не дойдем до начальной вершины.

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