Всем привет! Я реализовал, похоже, собственный алгоритм поиска кратчайшего пути с отрицательными ребрами графа.
Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)
Додумался я до него путем модификации классического Дейкстры. Прошу адекватно отнестись к содержимому, ибо это моя первая статья, и, возможно, я ничего не придумывал и, вообще, этот алгоритм не работает вовсе (но по многочисленным тестам он работает правильно).
Повторюсь, алгоритм работает с отрицательными ребрами графа (но не с циклическими отрицательными). Чем этот алгоритм отличается от известного Беллмана-Форда?
Эвристической сложностью! У известного алгоритма сложность составляет O(En), где n - количество узлов, Е - количество ребер. У "моего" алгоритма такая же ассимптотическая сложность. Но по моим расчетам худшая сложность в большинстве случаев не достигается. А у Беллмана-Форда худших случаев намного больше (об этом далее). Более того, в среднем алгоритм не превышает оригинальной сложности алгоритма Дейкстры, а именно O(n2+E). Об этом тоже напишу далее. Реализация на языке Python:
P.S.
В статье исправлены многие моменты, спасибо сообществу за тест-кейсы и подсказки. Некоторые комментарии не будут актуальными (в том числе саркастически-оскорбительные), т.к. я считаю, что доказал работоспособность алгоритма.
Реализация
Итак, у нас есть граф с отрицательным ребром между 2-м и 5-м узлом. Наша задача - найти кратчайший путь от источника (1-го узла) до 9-го узла (либо до любого другого достижимого).
Граф будет храниться в виде хэш таблицы, где:
graph = {
нода_1_(источник): {сосед_1: вес до него, сосед_2: вес до него, ...},
нода_2: {сосед_1: вес до него, сосед_2: вес до него, ...},
...
}
graph = {
1: {2: 10, 3: 6, 4: 8},
2: {7: 11, 4: 5, 5: -4},
3: {5: 3},
4: {7: 12, 3: 2, 5: 5, 6: 7},
5: {6: 9, 9: 12},
6: {8: 8, 9: 10},
7: {6: 4, 8: 6, 9: 16},
8: {9: 15},
9: {}
}Важно! Нужно писать узлы графа в порядке их отдаленности от источника. Т.е. сперва описываем первых соседей источника. После того, как описали их, приступаем к следующим соседям соседей. Т.е. описываем поуровнево, будто это не взвешенный граф, а обыкновенное дерево, где реализовываем поиск в ширину. В Python словари являются упорядоченными (начиная с версии 3.6), поэтому нам не стоит прибегать к другим структурам данных, типа Ordered dict из модуля collections.
Можно описать граф матрицей смежностей, но мне так проще.
P.S. Тот, кто задается подобным вопросом:
Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено.
Заранее отвечаю.
Хорошо, буду от вашей структуры отталкиваться. У нас какая задача? Найти кратчайший путь из точки А в точку В. Находим в вашем представлении графа точку А и смотрим на его соседей. Потом находим этих соседей и смотрим их соседей и т.д. Вот это "находим" в вашей беспорядочной структуре будет за N выполняться N раз. Это будет в том случае, если ноды у вас просто беспорядочно расположены в массиве (если вы используете эту структуру данных для хранения). Обычно в программе номер ноды совпадает с номером ячейки в массиве, что позволяет получить к этой ноде доступ за константу. В алгоритме Дейкстры (не я придумал его) как раз таки задача решается именно таким представлением графа, где номер ноды (или буква в лексиграфическом порядке) совпадает с номером ячейки в массиве. То, как вы пытаетесь представить граф - это по сути выстрел себе в ногу. Если отталкиваться от реальной жизни, нужно еще реализовать построение такой структуры графа. Условно ты находишься на перекрестке 1, мне надо в перекресток 10. А дай ка гляну, какие там дороги исходят из перекрестка 7 и запишу. Хотя можно было на второе место записать дороги перекрестка 2. В общем, замечание ваше понятно, но это всё общепринятая условность представления данных графа, я это не придумывал.
Поиск в ширину же выполнится за линейное время, поэтому он никак не увеличивает сложность алгоритма.
Допустим, если дана задача, где на вход подается граф вида: input_graph = [[узел_2, узел_5, вес до узла_5], [узел_7, узел_1, вес до узла_1] ...], то код построения моей структуры будет такой:
from collections import deque
arr = [[] for _ in range(n + 1)]
graph = {}
for item in input_graph:
arr[item[0]].append((item[1], item[2]))
queue = deque()
graph[1] = {}
for i in arr[k]:
neighbor = i[0]
graph[1][neighbor] = i[1]
queue.append(neighbor)
while queue:
current = queue.popleft()
if current not in graph:
graph[current] = {}
for i in arr[current]:
neighbor = i[0]
if neighbor not in graph:
graph[i[0]] = {}
queue.append(neighbor)
graph[current][neighbor] = i[1]С этим разобрались, идем дальше.
Так же нам понадобится еще 2 хэш таблицы.
Минимальные веса от источника до этой ноды в виде:
costs = {
нода_1_(источник): 0,
нода_2: infinity,
нода_3: infinity,
...
}
Заполнять и обновлять мы ее будем по мере прохождения по "детям" узлов.
costs = {} # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)Таблица родителей нод, от которых проходит кратчайший путь до этой ноды:
parents = {} # {Нода: его родитель}Ее так же будем заполнять и обновлять по мере прохождения по детям узлов.
Как и в алгоритме Дейкстры, будем отмечать еще неизвестные до узлов расстояния бесконечностью. Инициализируем эту переменную:
infinity = float('inf') # Бесконечность (когда минимальный вес до ноды еще неизвестен)Далее создаем пустое множество. Там будут храниться обработанные узлы (что значит "обработанные", поясню далее, а пока просто создаем множество)
processed = set() # Множество обработанных нодВведем новую структуру данных - список очередности обработки узлов графа.
lst = deque([key for key in graph.keys()]) # Формируем очередность прохождения узлов графаПриступим к самому алгоритму!
-
Начинаем с источника (первого узла). Смотрим на веса всех его соседей в таблице costs. Путь до них бесконечный, а любое число уже меньше бесконечности, поэтому обновляем веса. Так же вносим родителей всех узлов, т.к. мы обнаружили путь до ноды короче. Когда посмотрели всех соседей, вносим наш рассматриваемый узел в множество обработанных узлов processed (этот узел мы не будем обрабатывать в дальнейшем).
-
Здесь важный момент и отличие от алгоритма Дейкстры. Мы будем смотреть не минимальный по весу необработанный узел, а смотреть вообще ВСЕХ соседей поочередно. Т.е. у нас есть соседи после первого этапа алгоритма.
Мы поочередно так же будем искать уже их соседей и обновлять минимальные веса. Если же достижимый вес окажется меньше, чем внесенный в таблицу, то мы его заменяем. Так же заменяем его родителя в таблице parents.
Когда посмотрели всех соседей, вносим узел в множество обработанных. Т.е. множество обработанных - это те узлы, у которых мы рассмотрели всех его соседей! -
И так повторяем поуровнево (не приступаем к соседям соседей, пока не обработаем первых соседей), пока не будут обработаны все узлы.
-
Список очередности будет служить нашей итерабельной последовательностью первого цикла. Зачем? Если вдруг у ноды соседом будет уже обработанная нода, то мы эту ноду снова будем обрабатывать, т.к. веса детей могут стать меньше.
Код:
from collections import deque
graph = {
1: {2: 10, 3: 6, 4: 8},
2: {7: 11, 4: 5, 5: -4},
3: {5: 3},
4: {7: 12, 3: 2, 5: 5, 6: 7},
5: {6: 9, 9: 12},
6: {8: 8, 9: 10},
7: {6: 4, 8: 6, 9: 16},
8: {9: 15},
9: {}
}
lst = deque([key for key in graph.keys()]) # Формируем очередность прохождения узлов графа
parents = {} # {Нода: его родитель}
costs = {} # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)
infinity = float('inf') # Бесконечность (когда минимальный вес до ноды еще неизвестен)
processed = set() # Множество обработанных нод
while lst:
node = lst.popleft()
if node not in processed: # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
for child, cost in graph[node].items(): # Проходимся по всем детям
new_cost = cost + costs.get(node,
0) # Путь до ребенка = путь родителя + вес до ребенка (если родителя нет, то путь до него = 0)
min_cost = costs.get(child,
infinity) # Смотрим на минимальный путь до ребенка (если его до этого не было, то он беск.)
if new_cost < min_cost: # Если новый путь будет меньше минимального пути до этого,
costs[child] = new_cost # то заменяем минимальный путь на вычисленный
parents[child] = node # Так же заменяем родителя, от которого достигается мин путь
if child in processed: # UPDATE: если ребенок был в числе обработанных
lst.append(child) # Вновь добавляем эту ноду в список для того, чтобы обработать его заново
processed.remove(child) # Удаляем из обработанных
processed.add(node) # Когда все дети (ребра графа) обработаны, вносим ноду в множество обработанных
print(f'Минимальные стоимости от источника до ноды: {costs}')
print(f'Родители нод, от которых исходит кратчайший путь до этой ноды: {parents}')
# -> Минимальные стоимости от источника до ноды: {2: 10, 3: 6, 4: 8, 7: 20, 5: 6, 6: 15, 9: 18, 8: 23}
# -> Родители нод, от которых исходит кратчайший путь до этой ноды: {2: 1, 3: 1, 4: 1, 7: 4, 5: 2, 6: 4, 9: 5, 8: 6}Мы получили кратчайшие расстояния от источника до каждого достижимого узла в графе, а так же родителей этих узлов. Как же нам построить цепочку интересующего нас пути от источника до 9-ой ноды (либо до любой другой достижимой)? Ответ в коде ниже:
def get_shortest_path(start, end):
'''
Проходится по родителям, начиная с конечного пути,
т.е. ищет родителя конечного пути, потом родителя родителя и т.д. пока не дойдет до начала пути.
Тем самым мы строим обратную цепочку нод, которую мы инвертируем в конце, чтобы получить
истинный кратчайший путь
'''
parent = parents[end]
result = [end]
while parent != start:
result.append(parent)
parent = parents[parent]
result.append(start)
result.reverse()
shortest_distance = 0
for i in range(len(result)-1): # Узнаем кратчайшее расстояние
node_1 = result[i]
node_2 = result[i + 1]
shortest_distance += graph[node_1][node_2]
result = map(str, result) # В случае если имена нод будут числами, а не строками (для дальнейшего join)
print(f'Кратчайший путь от {start} до {end}: {shortest_distance}')
return result
shortest_path = get_shortest_path(start=1, end=9)
print('-->'.join(shortest_path))
# -> Кратчайший путь от 1 до 9: 18
# -> 1-->2-->5-->9Итак, мы нашли кратчайший путь до 9 узла, и обратите внимание, он проходит через ребро с отрицательным весом! Т.е. нас теперь не пугает наличие такого ребра, в отличие от оригинальной Дейкстры.
Еще деталь такая. При реализации классической Дейкстры, в случае, когда поиск МИНИМАЛЬНОГО по весу узла совпадет с нашим конечным целевым узлом,
то мы можем прервать дальнейшую обработку, т.к. мы уже нашли кратчайший путь до интересующего узла. В "моем" же алгоритме мы все равно будем обрабатывать все узлы.
Сложность
Что касается сложности данного алгоритма, то в наихудшем случае она будет такая же, как у Беллмана-Форда - O(N*E). Но я так и не нашел наихудший случай. Во всех случаях, которые я тестировал, он работал быстрее Беллмана-Форда. Давайте рассуждать.
Смоделируем ситуацию "в лоб". Посчитаем количество операций на наихудшем графе, который мне прислали, где алгоритм чувствуте себя несколько хуже, чем на других примерах. Пример графа (извиняюсь за ручной рисунок)
graph = {
1: {3:10, 2:1},
3: {5:10, 4:1 },
2: {3:1},
5: {7:10, 6:1 },
4: {5:1},
7: {9:10, 8:1},
6: {7:1},
9: {},
8: {9:1},
}
cycle_count = 0
processed = set() # Множество обработанных нод
while lst:
node = lst.popleft()
cycle_count += 1
if node not in processed: # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
for child, cost in graph[node].items(): # Проходимся по всем детям
new_cost = cost + costs.get(node,
0) # Путь до ребенка = путь родителя + вес до ребенка (если родителя нет, то путь до него = 0)
min_cost = costs.get(child,
infinity) # Смотрим на минимальный путь до ребенка (если его до этого не было, то он беск.)
if new_cost < min_cost: # Если новый путь будет меньше минимального пути до этого,
costs[child] = new_cost # то заменяем минимальный путь на вычисленный
parents[child] = node # Так же заменяем родителя, от которого достигается мин путь
if child in processed: # UPDATE: если ребенок был в числе обработанных
lst.append(child) # Вновь добавляем эту ноду в список для того, чтобы обработать его заново
processed.remove(child) # Удаляем из обработанных
processed.add(node) # Когда все дети (ребра графа) обработаны, вносим ноду в множество обработанных
print(f'Количество операций: {cycle_count}')
# -> Количество операций: 30
# По Беллману-Форду было бы: 9*12=108 судя по формулеПо Беллману-Форду количество операций, судя по формуле, превышает более чем в 3 раза!
Вы можете сказать: "да это просто граф такой попался". Что-ж рассмотрим граф, который является 100% наихудшим случаем для Беллмана-Форда, судя по информации из открытых источников.
Представим такого вида линейный граф: 1-->2-->3-->4-->5. Где каждое ребро имеет вес 1. По Беллману-Форду кол-во операций свелось бы как раз к его формуле (наихудшему случаю), а именно 5*4=20. В моем алгоритме:
graph = {
1: {2:1},
2: {3:1},
3: {4:1},
4: {5:1},
5: {},
}
# -> Количество операций: 4Т.е. по сути алгоритм выполнился линейно за O(E).
Если я что-то неправильно сделал, может быть, глупость совершил, что в "лоб" посчитал количество операций, то с радостью выслушаю, в чем мой "косяк". Но вроде как взял наихудшие случаи.
Что касается алгоритма классического Дейкстры, то его сложность не сильно лучше. НО! У него есть реализация с двоичной и фибоначчиевой куч. Вот реализация с помощью таких структур дает сильный буст этого алгоритма. Поэтому, если в задаче нет отрицательных ребер, то следует использовать именно такие алгоритмы, нежели мой. Вы в этом убедитесь в следующем разделе.
Стресс тесты
Итак, после реализации алгоритма мне прислали интересную задачу (отдельное спасибо за нее) с очень и очень каверзными тестами.
Обратите внимание! В этой задаче будут присутствовать узлы, у которых несколько ребер с разными весами направлены на один и тот же узел. Выглядит это вот так:
Это не простой граф. Называется он - мультиграф. С таким графом не справится ни один дефолтный алгоритм, поэтому придется обрабатывать такие случаи, что приведет к дополнительным ресурсным расходам. Но да ладно, это не проблема. А проблема в том, что если обратить внимание на входные данные, то можно слегка удивиться:
Количество узлов - 100к
Количество ребер - 200к
Максимальные веса ребер - 1 млрд
Очень даже не дурно для такой задачи. Что ж, я ее решил своим алгоритмом! Давайте обсудим по порядку. Результаты можете сами проверить, там сам код, время выполнения и правильность ответа. Я сравнивал мой алгоритм с классическим алгоритмом Дейкстры и с Дейкстрой, реализованном на двоичной куче. Запускал на процессоре Ryzen 7 5800X. С временем там сильно интересно! Ссылка на результаты с решениями. Ссылка на саму задачу. Обратите внимание, я взял тесты, где максимальное количество данных. Простые тесты я не включал в расчет, они и так проходят. P.S. не пытайтесь пихнуть мою реализацию алгоритмов в проверочную систему на питоне. Код проверку не пройдет, т.к. упрется в ограничение в 1 сек. Даже самый быстрый из реализованных алгоритмов не уложится ко времени во всех тестах (я пробовал). Возможно, реализация на С++ позволит это сделать, но я не знаком с ним. Возможно, сможете оптимизировать код (реализованный на куче) так, что он сможет пройти проверку. Теперь обсудим результаты.
Если кратко сделать выводы, то мы увидим, что задача, действительно, очень каверзная. В худшем случае обработка будет на 100 000 узлах и 200 000 ребрах! Если перевести все это в количество операций (причем не самых дешевых!), то имеем:
-
Классический Дейкстра (n^2 + E) займет 10^5*10^5 + 2*10^5 = 10млрд+200к операций.
-
Дейкстра с кучей (Elogn) займет 2*10^5 * 17 = 3.4 млн
-
Мой алгоритм (E*n) займет 2*10^5 * 10^5 = 20 млрд операций.
Видим, что для этой задачи мой алгоритм не подходит. Более того, не подходит и классическая Дейкстра. И даже, в некоторых тестах Дейкстра с кучей тоже не зашла! Плюс там дополнительное время уходит на обработку мультиграфа. Тесты все алгоритмы проходят долго, а иногда очень долго. Но если заметить, в среднем мой алгоритм даже чуточку быстрее прошел, чем классик Дейкстра (бывало и сильно медленнее, но реже). Так что, эвристическая сложность, считаю, все равно не плохой. Вот это задача так задача ;)
Самое главное, она решена. Время среднее схоже с оригинальной Дейкстрой. С Беллманом-Фордом тем более будет время хуже. Not bad я считаю!
Что ж, я решил еще одну задачу так же 3-мя способами на литкоде. Результаты ниже:
-
Мой алгоритм:
Hidden text
from collections import deque
class Solution:
def networkDelayTime(self, times, n, k):
arr = [[] for _ in range(n + 1)]
graph = {}
for item in times:
arr[item[0]].append((item[1], item[2]))
queue = deque()
graph[k] = {}
for i in arr[k]:
neighbor = i[0]
graph[k][neighbor] = i[1]
queue.append(neighbor)
while queue:
current = queue.popleft()
if current not in graph:
graph[current] = {}
for i in arr[current]:
neighbor = i[0]
if neighbor not in graph:
graph[i[0]] = {}
queue.append(neighbor)
graph[current][neighbor] = i[1]
lst = deque([key for key in graph.keys()])
parents = {}
costs = {}
infinity = float('inf')
processed = set()
while lst:
node = lst.popleft()
if node not in processed:
for child, cost in graph[node].items():
new_cost = cost + costs.get(node,
0)
min_cost = costs.get(child,
infinity)
if new_cost < min_cost:
costs[child] = new_cost
parents[child] = node
if child in processed:
lst.append(child)
processed.remove(child)
processed.add(node)
def get_shortest_path(start, end):
parent = parents.get(end, 'No')
if parent == 'No':
return 'No'
result = [end]
while parent != start:
result.append(parent)
parent = parents[parent]
result.append(start)
result.reverse()
shortest_distance = 0
for i in range(len(result) - 1):
node_1 = result[i]
node_2 = result[i + 1]
shortest_distance += graph[node_1][node_2]
return shortest_distance
max_distance = 0
for i in range(1, n + 1):
if k == i:
continue
distance = get_shortest_path(k, i)
if distance == 'No':
return -1
if distance > max_distance:
max_distance = distance
else:
return max_distance
-
Классический Дейкстра:
Hidden text
from collections import deque
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
arr = [[] for _ in range(n + 1)]
graph = {}
for item in times:
arr[item[0]].append((item[1], item[2]))
queue = deque()
graph[k] = {}
for i in arr[k]:
neighbor = i[0]
graph[k][neighbor] = i[1]
queue.append(neighbor)
while queue:
current = queue.popleft()
if current not in graph:
graph[current] = {}
for i in arr[current]:
neighbor = i[0]
if neighbor not in graph:
graph[i[0]] = {}
queue.append(neighbor)
graph[current][neighbor] = i[1]
infinity = float("inf")
costs = {}
parents = {}
processed = set()
for v in graph[k]:
costs[v] = graph[k][v]
parents[v] = k
def find_lowest_cost_node(costs):
lowest_cost = infinity
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs.get(node, infinity)
neighbors = graph[node]
for q in neighbors.keys():
new_cost = cost + neighbors[q]
old_cost = costs.get(q, infinity)
if old_cost > new_cost:
costs[q] = new_cost
parents[q] = node
processed.add(node)
node = find_lowest_cost_node(costs)
max_val = 0
for i in range(1, n + 1):
if i == k:
continue
value = costs.get(i, 'No')
if value == 'No':
return -1
if value > max_val:
max_val = value
return max_val
-
Дейкстра с кучей:
Hidden text
import heapq,sys
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj = defaultdict(list)
for t in times:
adj[t[0]].append((t[2],t[1]))
q=[]
heapq.heapify(q)
dist = [sys.maxsize]*(n)
dist[k-1]=0
heapq.heappush(q,(0,k))
while q:
d,u = heapq.heappop(q)
for weight,v in adj[u]:
if dist[v-1]>dist[u-1]+weight:
dist[v-1]=dist[u-1]+weight
heapq.heappush(q,(dist[v-1],v))
for i in range(len(dist)):
if dist[i]==sys.maxsize:
return -1
return max(dist)
Как мы видим, время выполнения одинаковое, возможно, можно че-то улучшить, где-то оптимизировать и т.д. но время сильно не улучшится, т.к. данных не 20 млрд :)
НО! Мой то алгоритм еще и с отрицательными ребрами может!
Выводы
Алгоритм работает! Причем с неплохой скоростью. Если учитывать то, что еще и с отрицательными весами работает - то это, я считаю, победа! Но если в задаче указано, что нет отрицательных ребер, то нужно все-таки пользоваться Дейкстрой с кучей. Если мало данных или задача сама не знает, есть ли там отрицательные веса, то можно смело пользоваться моим (наверное, так можно уже сказать) алгоритмом.
Всем спасибо, кто поддерживал! Все хейтеры и "элиты" хабра, можете дальше пытаться меня оскорбить или посмеяться надо мной. Если кто найдет интересные задачи, можете присылать. Всем добра! ;)
Автор: carbon2409
