Практика: поиск путей минимального веса

Введение

Ранее вы изучили алгоритм поиск в ширину, позволяющий находит кратчайшие пути в невзвешенном графе. Однако, в случае взвешенных графов BFS будет не всегда давать корректный ответ, т.к. он по факту находит путь, содержащий минимальное количество ребер. Перед нами будет стоять задача нахождения пути с наименьшей суммой весов ребер в нем.

Алгоритм Флойда-Уоршалла

Для начала рассмотрим алгоритм Флойда (Флойда-Уоршалла). Его отличительной особенностью является то, что он умеет находить кратчайшие расстояния между всеми парами вершин. Но за это приходится платить временем работы, О(N^3). Идея заключается в следующем: мы будем перебирать все возможные тройки вершин (i, j, k) и пытаться улучшить путь из i в j, проходя через k.

# Считываем граф, преобразуем его в матрицу смежности, которую храним в d
# Отсутствие ребра помечаем каким-нибудь заведомо большим числом
# Считаем, что n - кол-во вершин, вершины пронумерованы от 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

Алгоритм Дейкстры

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

1. На каждой итерации алгоритм среди непомеченных вершин вибирает с наименьшим до нее расстоянием;
2. Помечает вершину как посещенную.
3. Пытается улучшить расстояние до смежных с ней вершин;

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

# считываем граф, преобразуем его в список смежности, который храним в graph
# INF - заведомо большое число
d = [INF]*n  # Считаем, что n - кол-во вершин, вершины пронумерованы от 0
d[s] = 0  # s - стартовая вершина
used = [False]*n
while True:
    u = -1
    for i in range(n):
        if not used[i] and (u == -1 or d[u] > d[i]):
            u = i
    if u == -1:
        break
    used[u] = True
    for v, w in graph[u]:
        d[v] = min(d[v], d[u] + w)

Время работы алгоритма зависит от того, как быстро ищется минимум. В приведенном выше варианте время работы O(N^2). Для ускорения алгоритма применяют кучу либо дерево отрезков. В обоих случаях время работы будет O((N+M) log N).

Алгоритм Форда-Беллмана

Алгоритм Форда-Беллмана будет последним рассмотренным алгоритмом, который, как и алгоритм Дейкстры, используется для поиска кратчайшего расстояния от одной вершины до остальных. Он является типичным алгоритмом ДП. Состояния описываются двумя параметрами и означают "длину кратчайшего пути, проходящего не более, чем по i ребрам, и заканчивающегося в вершине j".

# считываем граф, преобразуем его в список ребер, который храним в edges
d = [None]*n  # Считаем, что n - кол-во вершин, вершины пронумерованы от 0
d[s] = 0  # s - стартовая вершина
# INF - заведомо большое число
for i in range(n-1):
    for u, v, w in edges:
        if d[u] is not None:
            d[v] = min(INF if d[v] is None else d[v], d[u] + w)

Такой алгоритм работает O(N*M). Заметим несколько вещей:

1. Алгоритм работает корректно даже при наличии ребер отрицательного веса, -1 - валидное значение для расстояний, поэтому массив инициализировался с None;
2. Вернувшись в вершину, пройдя по циклу, расстояние до нее не может уменьшится (циклы отрицательного веса пока не рассматриваем);
3. Исходя из (2) для нахождения кратчайшего пути до всех вершин достаточно N-1 итерации, т.е. кратчайшие пути до всех вершин не содержат циклов.

Однако утверждение (2) справедливо, только когда нет циклов отрицательного веса, т.е. цикла, в которой растояния до вершин в нем будут каждый раз уменьшаться, если мы будем по нему гулять. Таким образом нам вообще не выгодно его заканчивать, а значит мы можем счиать, что кратчайшие расстояния до этих вершин будут -∞. Таким образом N-1 итерации не хватит чтобы посчитать кратчайшие расстояния. Поэтому мы можем внешний цикл увеличить на одну итерацию. Все вершины, расстояние до которых обновится на последней итерации, можем считать имеют расстояние -∞.

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