В том, что цель задачи там другая. Там нужно найти такой путь, чтобы посетить ВСЕ узлы за минимальное расстояние. Это NP полная задача, занимает факториальное время и в настоящий момент люди не смогли придумать алгоритм быстрее.
Что Вы имеете ввиду? Не помню такого описания. Структуру графа в примере реализована точно так же, как в Ваших примерах - в виде словаря словарей
Структура да, а порядок сделан неверно. Я написал код создания моей структуры, вручную теперь не нужно этого делать. Пользуйтесь этим кодом и не ошибетесь. Вручную придется вводить только список ребер, впрочем в задачах часто на вход подаются графы такой структуры.
Все расстояния вывел неправильно, а Вы говорите корректно работает.
Странно, что у Вас неправильно выводится. Может быть у Вас граф какой-то необычный? Тот граф, который встроен в код в разделе обработки недостижимых нод работает корректно.
Вы несколько раз указывали, что это можно сделать обходом в ширину
Ну да, а что, это разве сортировка? Он за линейное время выполнится. Сортировка же за nlogn и то не всегда, в худшем случае n^2.
Неверно. 12 обработанных узлов во внешнем цикле
Да я вчера перед Вами извинился за ложную информацию, написал об этом. Я поздно заметил, что cycle_count стоял во внешнем цикле, я потом пересчитал все значения и вроде везде в коде исправил этот момент.
Вы неправильно понимаете, что такое сложность алгоритма
Да я понимаю, что такое сложность. Просто для наглядности считал количество операций. Если и там и там посчитать их, то можно что-то с чем-то наглядно сравнить, нежели просто формулу сложности смотреть. В той же быстрой сортировке сложность nlogn, но иногда n^2, когда массив "почти" отсортирован уже. Так как тогда сравнить, например, обычную сортировку с быстрой? По мне наглядно посчитать кол-во операций, сделанных там и там, пусть и не будет соответствовать формуле. Да, я считал по формуле кол-во операций, скоро я дополню статью сравнением скорости Spfa и Левита, а так же стандартного Беллмана-Форда. Там будет выглядить все нагляднее, ожидайте.
Это и есть алгоритм Левита
Это не он, у него реализация несколько другая. Плюс ко всему время его выполнения по предварительным тестам существенно выше, чем мой алгоритм. Чуть позже это продемонстрирую. Так же я заметил, что в моем алгоритме есть "лишние" операции, без которых можно обойтись, тем самым ускорив его слегка. Сегодня буду дополнять и обновлять содержимое статьи.
Доброе утро! У меня статья обновлена, я ускорил момент с lst, взгляните еще раз. Что касается предложения вашего, звучит разумно, спасибо. Когда буду за машиной своей, попробую реализовать, благодарю!
P.S. Извиняюсь, неправильно посчитал количество операций. Самое большое количество - 60 операций, плюс более препроцессинг 20. Итого 80 против 100. Ну, наверное, можно назвать плохим случаем.
Если неправильно следовать алгоритму, то он и не будет правильно работать)) Специально для вас и для всех, кто так думает я включил подробнейшее пояснение, как правильно самостоятельно реализовать структуру графа. Ознакомьтесь еще раз, ваше высказывание не соответствует действительности.
Чтобы избавиться от этой проблемы, нужно ...
Ничего не нужно там делать, все там сделано. Отдельно написал про обработку недостижимых нод их вывод, все корректно работает.
Алгоритм требует предварительной сортировки узлов по расстоянию от начального узла в "штуках рёбер"
Никакой сортировки там не нужно, все работает без нее.
Плохим случаям для Вашего алгоритма будет:
С этим графом максимальное количество операций будет - 12. Плюс еще препроцессинг на 5 операций. Итого 17 операций против "наихудших" EV = 20*5=100 операций. Это ни разу не плохой случай ;)
Все что написано далее не требует никаких изменений в моем алгоритме. Вы его хотите переделать под алгоритм Левита, только зачем? Кстати спасибо за наводку, я не был знаком с этим алгоритмом. Я познакомился с ним, оформил реализацию и по предварительным тестам он работает намного медленнее. Плюс там, если не ошибаюсь, даже с реализацией 2-х очередей, в некоторых редких случаях сложность экспоненциальная. Я планирую сравнить Форда-Беллмана с оптимизацией, Левита и свой алгоритм на скорость выполнения стресс тестов. Следим за ситуацией, спасибо!
Да, я так и понял, что такой вид примет структура.
Вам же в алгоритме не надо брать ребро между двумя заданными вершинами.
Когда проходишь по всем ребрам в первой части алгоритма, то да. Но когда вычисляешь расстояние, мне как раз-таки это и нужно! Я вам специально прислал кусок кода, где мне это нужно, посмотрите внимательнее.
Да, на графе с кучей параллельных ребер ваш алгоритм будет работать дольше и потребует больше памяти. Но не потому, что параллельные ребра какие-то особенные, а потому что там ребер больше.
Смотрите, заранее удалить ребро в моей реализации будет дешевле, чем обрабатывать его более тяжелой операцией. Поэтому идея не самая плохая. По сравнению с известными алгоритмами уже быстрее будет по идее. Это будут "не одинаковые" EV. Там E уже по сути будет меньше.
Вообще, ваша идея иметь изначальный список всех вершин в порядке удаления - весьма странная.
Повторюсь, прочитайте еще раз статью, пожалуйста. Чувствую, вы суть не до конца поняли. Без этого списка я бы не построил свою структуру графа. В той же Дейкстре если создается матрица смежностей, то это двумерный список, где i-ый элемент соответствует i-му узлу. Поэтому если вы говорите, что это идея странная, то значит и у известных алгоритмов она тоже странная. Впрочем, я писал об этом, можете ознакомиться еще раз.
Да, пардон, виноват, обрабатывают. Я просто привык к своей структуре графа, что забыл уже, что в других алгоритмах она другая и там он просто в процессе выполнения алгоритма сам по себе выберет меньшую из ребер. Но стоимость операций от этого не снизится, т.к. по сути это будет такой же лишний проход, как и "оставления" меньшего ребра в моей реализации.
формат хранения графа заменить со словаря словарей на словарь списков (куда ведет ребро и какой оно длины)
В моем алгоритме это приведет либо к росту сложности, либо к росту памяти. Поясню, смотрите, если сделать, как вы предлагаете, тогда придется изменять функцию построения кратчайшего пути:
for i in range(len(result)-1): # Узнаем кратчайшее расстояние
node_1 = result[i]
node_2 = result[i + 1]
shortest_distance += graph[node_1][node_2]
Последняя строка у меня выполнится за константу, т.к. словарь словарей. Если был бы словарь списков, тогда мы node_2 искали бы линейным поиском, что привело бы к ухудшению эвристической сложности.
Если список инициализировать количеством узлов, чтобы за константу получить вторую ноду, тогда у нас было бы n списков из n элементов. Ухудшение по памяти.
Вывод: с мультиграфами в любом случае немножко похуже, чем с простыми графами. Мое решение этой проблемы вполне себе рабочее, я считаю. Возможно, даже и дешевле, нежели у Дейкстры и Беллмана-Форда.
Не стоит заявлять, что в тесткейсах графы какие-то неправильные.
Ок. Проверил информацию в интернете, такие графы существуют, но называются они мультиграфами. Мой же алгоритм в исходном исполнении рассчитан на простые графы. Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы. Самому эту фичу прикручивать нужно. Но да ладно не совсем проблема это.
Ложные ответы отсутствуют - а вот это утерждение надо бы подтвердить)
Я не поленился и сделал это. И знаете что? Все тесты пройдены! Результаты можете сами проверить, там сам код, время выполнения и правильность ответа. Я сравнивал мой алгоритм с классическим алгоритмом Дейкстры и с Дейкстрой, реализованном на куче. Запускал на процессоре Ryzen 7 5800X. С временем там сильно интересно! Ссылка на результаты.
Если кратко сделать выводы, то мы увидим, что задача, действительно, очень каверзная. В худшем случае обработка будет на 100 000 узлах и 200 000 ребрах! Если перевести все это в количество операций (причем не самых дешевых!), то имеем:
Видим, что для этой задачи мой алгоритм не подходит! Более того, не подходит и классическая Дейкстра. И даже, в некоторых тестах Дейкстра с кучей тоже не зашла! Плюс там дополнительное время уходит на обработку мультиграфа. Тесты все алгоритмы проходят долго, а иногда очень долго. Но если заметить, в среднем мой алгоритм даже чуточку быстрее прошел, чем классик Дейкстра (бывало и сильно медленнее, но реже). Так что, эвристическая сложность, считаю, все равно не плохой.
Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit - выйдет. Ассимптотика не изменится. Поверьте, если ваш алгоритм вылезает за временные ограничения - 99.9% вероятность в том, что ваш алгоритм имеет неправильную ассимптотику. Только в олимпиадах высокого уровня временные ограничения задаются так, чтобы максимально быстрый алгоритм еле-еле влезал в них. Вот там да, бывают ситуации, когда код на С++ влезет, а его аналог на питоне - нет. Но это не ваш случай.
Ну попробуйте сами тогда написать на СPython эту задачу. Алгоритмы известные есть, ассимптотика у них известная. Я написал максимально быстрый алгоритм, который знаю, и он все равно не зашел. Хочу посмотреть на вашу реализацию, как вы в 1 сек на питоне вместите 3.5 млн недешевых операций. И не надо писать, мол "зачем мне это нужно, у меня своих дел полно и т.д." Вы мне эту задачу дали, сказав "когда решите эту, тогда приходите сюда со своим алгоритмом", и не поленились найти эту задачу, а так же заранее написать, что алгоритм скорее всего не рабочий и оценен неправильно. Я не поленился решить ее 3-мя способами. Так попробуйте сами решить, прежде чем такое говорить, на известных алгоритмах. Может быть, у вас получится решить, возможно я неэффективную реализацию писал.
Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма) - но ведь изначально посыл поста был в том, что вы изобрели новый алгоритм, который лучше Дейкстры :) А выходит, что нет.
Вы точно внимательно читали статью? В каком месте я такое говорил? Я наоборот подчеркивал, что если отрицательных весов нет, нужно Дейкстрой пользоваться. "
Выводы
В случае, если нам могут встретится отрицательные ребра в графе, можно пользоваться данным алгоритмом. Можно воспользоваться и известным Беллмана-Форда, кому как нравится, но мне показался он более сложным в понимании. В случае, если нам известно, что граф не содержит отрицательных весов, тогда можно смело пользоваться Дейкстрой.
"
Он имеет преимущество над скоростью выполнения Беллмана-Форда. Над Дейкстрой имеет преимущество возможностью использования с отрицательными ребрами (ну иногда скоростью тоже, если классик Дейкстра, о чем я писал выше).
вы не молодец, потому что продолжаете обвинять кого угодно (нюансы языка, спорные особенности задачи...) в том, что ваше решение не проходит.
Про задачу я уже сказал, думаю, суть уловили. По вашей логике можно дать задачу которая решается одним и только одним алгоритмом, и сказать "вот реши его другим алгоритмом! Не решишь, уложившись в ограниченное время - значит не работает он."
А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще)
Что ж, я решил еще одну задачу так же 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)
Как видим, мой алгоритм прошел все тесты и по времени не отличается от других известных. НО! Мой то еще с отрицательными весами умеет! Так что делаю, как вы говорите, вывод, что мой алгоритм рабочий.
Пожалуй, обновлю скоро статью, включу туда тесты, исправлю некоторые моменты. Спасибо за задачу, удачи!
А что, собственно, не так? Я пояснил этот момент, он никак не влияет на оценку сложности. Или вам смешно от того, что не знакомы с поиском в ширину? Какие злые люди, лишь бы вставить свои 5 грязных копеек. Судя по вашему профилю, вы эти копеечки пытаетесь вставить всюду. Будьте добрее!
Здравствуйте! Спасибо за задачу. Прежде чем обсудить ее, напишу сразу - задачу я решил с моим алгоритмом, но есть нюансы. А теперь к самим нюансам:
После ознакомления с условием задачи я обратил внимание на их тест-кейс:
В их тест-графах присутствуют узлы, у которых 2 разных по весу ребра направлены на один и тот же узел. Т.е. в схеме это выглядит вот так:
От первого узла к третьему 2 ребра разных весов. Я не специалист по графам, поэтому не могу сказать корректен ли этот пример. По моей логике не совсем, но если этому имеет место быть, то ок.
Из первого нюанса следует то, что мне пришлось обрабатывать такие случаи, т.к. в моем алгоритме не предусмотрены такие структуры графов. Мне приходилось записывать в мою структуру графа меньшую из ребер, а поиск меньшего занимало определенное количество ресурсов.
Я пробовал кидать решение на CPython и PyPy. Обратил внимание на то, что там присутствуют тесты с 10^5 узлов и 10^6 ребер. Ограничение 1 сек. Для стандартного питона это ну ооочень тяжко. Для PyPy уже полегче (практически в 2 раза быстрее). Результаты отправки:
CPython
PyPy
Обратите внимание! Ложные ответы отсутствуют (там 23 теста, но у них так же Time Limit). Причем если посмотреть на результаты времени тестов, то можно заметить, что PyPy быстрее примерно в 2 раза. Смотрим на 11 тест. У нас ограничение в 1 сек. Наш тест занял примерно пол секунды на PyPy с верным ответом. А в CPython он вышел за пределы времени (0.5*2=1). Причем код один и тот же. Получается, алгоритм не выдает неверные решения, как вы сказали, а просто выходит за пределы времени. Это не означает что алгоритм не рабочий! Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit (но я не знаю этот язык). Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма), там в условиях отсутствуют ребра с отрицательным весом.
Таким образом, я делаю вывод, что алгоритм работает, но нюансы языка и спорная особенность задачи не позволяют ее сдать в эту систему. Добра Вам!
Hidden text
from collections import deque
n, m = map(int, input().split())
arr = [[] for _ in range(n+1)]
graph = {}
for _ in range(m):
a, b, c = map(int, input().split())
arr[a].append((b, c))
queue = deque()
graph[1] = {}
for i in arr[1]:
neighbor = i[0]
is_include_before = graph[1].get(neighbor, False)
if not is_include_before:
graph[1][neighbor] = i[1]
queue.append(neighbor)
else:
graph[1][neighbor] = min(is_include_before, i[1])
while queue:
current = queue.popleft()
if current not in graph:
graph[current] = {}
for i in arr[current]:
if i[0] not in graph:
graph[i[0]] = {}
neighbor = i[0]
is_include_before = graph[current].get(neighbor, False)
if not is_include_before:
graph[current][neighbor] = i[1]
queue.append(neighbor)
else:
graph[current][neighbor] = min(is_include_before, i[1])
lst = [key for key in graph.keys()] # Формируем очередность прохождения узлов графа
parents = {} # {Нода: его родитель}
costs = {} # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)
infinity = float('inf') # Бесконечность (когда минимальный вес до ноды еще неизвестен)
cycle_count = 0
processed = set() # Множество обработанных нод
for node in lst:
if node not in processed: # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
for child, cost in graph[node].items(): # Проходимся по всем детям
cycle_count += 1
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) # Когда все дети (ребра графа) обработаны, вносим ноду в множество обработанных
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]
return shortest_distance
print(0, end=' ')
for i in range(2, n+1):
print(get_shortest_path(1, i), end=' ')
Надо математически доказать, что найдутся кратчайшие пути. Ввести какие-то инварианты, вроде "до вершин в обработанном множестве найдены кратчайшие пути". Показать, почему он поддерживается.
С этим беда у меня, я не сильный математик, чтобы доказать что-то, поэтому и пишу здесь. Знаю, что обычно доказывают по индукции или "от противного".
Если подсчитать, сколько раз вершины будут обработаны и вывести
Я ради интереса сделал это. Просто вставил счетчик операций в мой цикл и посмотрел на вашем примере графа. Кстати, спасибо за пример, алгоритм чувствует себя похуже других графов. Результат ниже:
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: {10: 1, 11: 10},
8: {9:1},
10: {11:1},
11: {}
}
cycle_count = 0
processed = set() # Множество обработанных нод
for node in lst:
if node not in processed: # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
for child, cost in graph[node].items(): # Проходимся по всем детям
cycle_count += 1
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}')
# -> Количество операций: 45
# По Беллману-Форду было бы: 9*8=72 судя по формуле
В нашем графе мы бы совершили 45 операций, вместо 72 (если судить по формуле).
Кроме того, нашел информацию, что Беллман-Форд имеет наихудшую сложность, которая предполагает ему формула, при линейном графе. Что имею в виду? Представим такого вида линейный граф: 1-->2-->3-->4-->5. Где каждое ребро имеет вес 1. По Беллману-Форду кол-во операций свелось бы как раз к его формуле, а именно 5*4=20. В моем алгоритме:
Если я что-то неправильно сделал, может быть, глупость совершил, что в "лоб" посчитал количество операций, то с радостью выслушаю, в чем мой "косяк". Но вроде как взял наихудшие случаи.
использование множеств и самосортирующихся списков - да-да, это всё тоже считается в оценке сложности
Какие "самосортирующиеся списки" вы имеете в виду, поясните, пожалуйста.
За счет ... хм, "бесплатного" множества, которое, как бы "сразу знает", а не перебирает всё, что в него накидано, при каждом запросе
В алгоритме операция с множеством осуществляется за константное время, там ничего не перебирается, а лишь проверяется наличие элемента в этом множестве. Напомню, множество в Python реализовано хэш таблицей.
Python не считается приемлемым для обучения базовым методам программирования
Здесь мне сказать нечего, очень и очень спорное выражение, пожалуй, не буду его развивать.
И вот что ещё важно. Реальный граф, по которому ищется путь - это тысячи узлов и, часто, намного больше. В таких ситуациях любое "оптимизация" вроде сортировок всех узлов - огромная вычислительная нагрузка.
Про это я уже написал, прочтите, пожалуйста, выше.
Здравствуйте! Вижу, Вы подкреплены в теме. Сейчас, к сожалению, нет возможности просмотреть и изучить вами присланный материал. Можете, пожалуйста, сказать, правильно ли я оценил сложность (N^2) и какова сложность уже известного алгоритма, о котором Вы упоминаете? Насколько помню, у Беллмана-Форда кубическая сложность, про модификацию его алгоритма я не слышал. Спасибо!
Я не математик, я вообще даже в техническом ВУЗе не учился. А учился я на биолога-химика. В IT сферу ушел, потому что мне с детства нравилась эта тема, но родители хотели, чтобы я был медиком :) В итоге математический бэкграунд у меня хромает. Поэтому и пишу здесь, в надежде найти людей компетентнее. Спасибо!
Хорошо, допустим, включу, но от этого общая сложность не изменится. Поиск в ширину за линейное время выполняется, если граф представлен в корректной структуре данных. Поправьте, если не прав. Спасибо!
Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено.
Хорошо, буду от вашей структуры отталкиваться. У нас какая задача? Найти кратчайший путь из точки А в точку В. Находим в вашем представлении графа точку А и смотрим на его соседей. Потом находим этих соседей и смотрим их соседей и т.д. Вот это "находим" в вашей беспорядочной структуре будет за N выполняться N раз. Это будет в том случае, если ноды у вас просто беспорядочно расположены в массиве (если вы используете эту структуру данных для хранения). Обычно в программе номер ноды совпадает с номером ячейки в массиве, что позволяет получить к этой ноде доступ за константу. В алгоритме Дейкстры (не я придумал его) как раз таки задача решается именно таким представлением графа, где номер ноды (или буква в лексиграфическом порядке) совпадает с номером ячейки в массиве. То, как вы пытаетесь представить граф - это по сути выстрел себе в ногу. Если отталкиваться от реальной жизни, нужно еще реализовать построение такой структуры графа. Условно ты находишься на перекрестке 1, мне надо в перекресток 10. А дай ка гляну, какие там дороги исходят из перекрестка 7 и запишу. Хотя можно было на второе место записать дороги перекрестка 2. В общем, замечание ваше понятно, но это все общепринятая условность представления данных графа, я это не придумывал.
Замените половину весов на отрицательные и посмотрите, что там посчитается.
И все будет работать, в чем подвох? Если вы хотите сделать отрицательный вес графу, который направлен обратно, то это будет отрицательный цикл, а я писал о том, что на таких графах алгоритм не работает (он уйдет в беск. минимизацию веса). На таком графе и дефолтный Беллмана-Форда не будет работать, в чем тогда Ваша претензия. Спасибо!
Я не очень понимаю значения глагола "хейтить", но полагаю, что оно было бы более применимо, если бы я например просто молча поставил минус.
Согласен, вы хотя бы рассказали, что не так, высказали ваше мнение, спасибо, учту.
Расстояние от 1 до 2 это 12 (1->4->3->2), а алгоритм посчитал 20
Я исправляю эту ситуацию. Подробнее ниже описал. Следим за ситуацией, как говорится :)
Каждая вершина обрабатывается во внутреннем цикле ровно один раз. Учитывая, что граф обрабатывается списками смежности, то суммарное количество итераций внутреннего цикла -- в точности количество ребер. Если быть более точным, то оценка O(V+E).
Слушайте, если это действительно так, т.е. пока что неработающий алгоритм работает за линейное время, то можно обработать ту проблему, которая ломает алгоритм и тогда сложность будет, если не ошибаюсь, составлять O(n^2). Сейчас есть исправленный код, я его тестирую, если все работает нормально, дополню статью. Становится еще интереснее!
Странно, что меня минусуют, ведь я воспринял комментарий так: "Ты питонист, ты не математик! Все питонисты - не математики! Так что не лезь в нашу нишу, программист!" Я и ответил соответствующе, м.б, если обидел, извини, конечно, но и ты меня задел, на самом деле.
В том, что цель задачи там другая. Там нужно найти такой путь, чтобы посетить ВСЕ узлы за минимальное расстояние. Это NP полная задача, занимает факториальное время и в настоящий момент люди не смогли придумать алгоритм быстрее.
Структура да, а порядок сделан неверно. Я написал код создания моей структуры, вручную теперь не нужно этого делать. Пользуйтесь этим кодом и не ошибетесь. Вручную придется вводить только список ребер, впрочем в задачах часто на вход подаются графы такой структуры.
Странно, что у Вас неправильно выводится. Может быть у Вас граф какой-то необычный? Тот граф, который встроен в код в разделе обработки недостижимых нод работает корректно.
Ну да, а что, это разве сортировка? Он за линейное время выполнится. Сортировка же за nlogn и то не всегда, в худшем случае n^2.
Да я вчера перед Вами извинился за ложную информацию, написал об этом. Я поздно заметил, что cycle_count стоял во внешнем цикле, я потом пересчитал все значения и вроде везде в коде исправил этот момент.
Да я понимаю, что такое сложность. Просто для наглядности считал количество операций. Если и там и там посчитать их, то можно что-то с чем-то наглядно сравнить, нежели просто формулу сложности смотреть. В той же быстрой сортировке сложность nlogn, но иногда n^2, когда массив "почти" отсортирован уже. Так как тогда сравнить, например, обычную сортировку с быстрой? По мне наглядно посчитать кол-во операций, сделанных там и там, пусть и не будет соответствовать формуле. Да, я считал по формуле кол-во операций, скоро я дополню статью сравнением скорости Spfa и Левита, а так же стандартного Беллмана-Форда. Там будет выглядить все нагляднее, ожидайте.
Это не он, у него реализация несколько другая. Плюс ко всему время его выполнения по предварительным тестам существенно выше, чем мой алгоритм. Чуть позже это продемонстрирую. Так же я заметил, что в моем алгоритме есть "лишние" операции, без которых можно обойтись, тем самым ускорив его слегка. Сегодня буду дополнять и обновлять содержимое статьи.
Доброе утро! У меня статья обновлена, я ускорил момент с lst, взгляните еще раз. Что касается предложения вашего, звучит разумно, спасибо. Когда буду за машиной своей, попробую реализовать, благодарю!
P.S. Извиняюсь, неправильно посчитал количество операций. Самое большое количество - 60 операций, плюс более препроцессинг 20. Итого 80 против 100. Ну, наверное, можно назвать плохим случаем.
Если неправильно следовать алгоритму, то он и не будет правильно работать)) Специально для вас и для всех, кто так думает я включил подробнейшее пояснение, как правильно самостоятельно реализовать структуру графа. Ознакомьтесь еще раз, ваше высказывание не соответствует действительности.
Ничего не нужно там делать, все там сделано. Отдельно написал про обработку недостижимых нод их вывод, все корректно работает.
Никакой сортировки там не нужно, все работает без нее.
С этим графом максимальное количество операций будет - 12. Плюс еще препроцессинг на 5 операций. Итого 17 операций против "наихудших" EV = 20*5=100 операций. Это ни разу не плохой случай ;)
Все что написано далее не требует никаких изменений в моем алгоритме. Вы его хотите переделать под алгоритм Левита, только зачем? Кстати спасибо за наводку, я не был знаком с этим алгоритмом. Я познакомился с ним, оформил реализацию и по предварительным тестам он работает намного медленнее. Плюс там, если не ошибаюсь, даже с реализацией 2-х очередей, в некоторых редких случаях сложность экспоненциальная. Я планирую сравнить Форда-Беллмана с оптимизацией, Левита и свой алгоритм на скорость выполнения стресс тестов. Следим за ситуацией, спасибо!
Да, я так и понял, что такой вид примет структура.
Когда проходишь по всем ребрам в первой части алгоритма, то да. Но когда вычисляешь расстояние, мне как раз-таки это и нужно! Я вам специально прислал кусок кода, где мне это нужно, посмотрите внимательнее.
Смотрите, заранее удалить ребро в моей реализации будет дешевле, чем обрабатывать его более тяжелой операцией. Поэтому идея не самая плохая. По сравнению с известными алгоритмами уже быстрее будет по идее. Это будут "не одинаковые" EV. Там E уже по сути будет меньше.
Повторюсь, прочитайте еще раз статью, пожалуйста. Чувствую, вы суть не до конца поняли. Без этого списка я бы не построил свою структуру графа. В той же Дейкстре если создается матрица смежностей, то это двумерный список, где i-ый элемент соответствует i-му узлу. Поэтому если вы говорите, что это идея странная, то значит и у известных алгоритмов она тоже странная. Впрочем, я писал об этом, можете ознакомиться еще раз.
Да, пардон, виноват, обрабатывают. Я просто привык к своей структуре графа, что забыл уже, что в других алгоритмах она другая и там он просто в процессе выполнения алгоритма сам по себе выберет меньшую из ребер. Но стоимость операций от этого не снизится, т.к. по сути это будет такой же лишний проход, как и "оставления" меньшего ребра в моей реализации.
В моем алгоритме это приведет либо к росту сложности, либо к росту памяти. Поясню, смотрите, если сделать, как вы предлагаете, тогда придется изменять функцию построения кратчайшего пути:
Последняя строка у меня выполнится за константу, т.к. словарь словарей. Если был бы словарь списков, тогда мы node_2 искали бы линейным поиском, что привело бы к ухудшению эвристической сложности.
Если список инициализировать количеством узлов, чтобы за константу получить вторую ноду, тогда у нас было бы n списков из n элементов. Ухудшение по памяти.
Вывод: с мультиграфами в любом случае немножко похуже, чем с простыми графами. Мое решение этой проблемы вполне себе рабочее, я считаю. Возможно, даже и дешевле, нежели у Дейкстры и Беллмана-Форда.
Ок. Проверил информацию в интернете, такие графы существуют, но называются они мультиграфами. Мой же алгоритм в исходном исполнении рассчитан на простые графы. Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы. Самому эту фичу прикручивать нужно. Но да ладно не совсем проблема это.
Я не поленился и сделал это. И знаете что? Все тесты пройдены! Результаты можете сами проверить, там сам код, время выполнения и правильность ответа. Я сравнивал мой алгоритм с классическим алгоритмом Дейкстры и с Дейкстрой, реализованном на куче. Запускал на процессоре Ryzen 7 5800X. С временем там сильно интересно! Ссылка на результаты.
Если кратко сделать выводы, то мы увидим, что задача, действительно, очень каверзная. В худшем случае обработка будет на 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 млрд операций.
Видим, что для этой задачи мой алгоритм не подходит! Более того, не подходит и классическая Дейкстра. И даже, в некоторых тестах Дейкстра с кучей тоже не зашла! Плюс там дополнительное время уходит на обработку мультиграфа. Тесты все алгоритмы проходят долго, а иногда очень долго. Но если заметить, в среднем мой алгоритм даже чуточку быстрее прошел, чем классик Дейкстра (бывало и сильно медленнее, но реже). Так что, эвристическая сложность, считаю, все равно не плохой.
Ну попробуйте сами тогда написать на СPython эту задачу. Алгоритмы известные есть, ассимптотика у них известная. Я написал максимально быстрый алгоритм, который знаю, и он все равно не зашел. Хочу посмотреть на вашу реализацию, как вы в 1 сек на питоне вместите 3.5 млн недешевых операций. И не надо писать, мол "зачем мне это нужно, у меня своих дел полно и т.д." Вы мне эту задачу дали, сказав "когда решите эту, тогда приходите сюда со своим алгоритмом", и не поленились найти эту задачу, а так же заранее написать, что алгоритм скорее всего не рабочий и оценен неправильно. Я не поленился решить ее 3-мя способами. Так попробуйте сами решить, прежде чем такое говорить, на известных алгоритмах. Может быть, у вас получится решить, возможно я неэффективную реализацию писал.
Вы точно внимательно читали статью? В каком месте я такое говорил? Я наоборот подчеркивал, что если отрицательных весов нет, нужно Дейкстрой пользоваться. "
Выводы
В случае, если нам могут встретится отрицательные ребра в графе, можно пользоваться данным алгоритмом. Можно воспользоваться и известным Беллмана-Форда, кому как нравится, но мне показался он более сложным в понимании.
В случае, если нам известно, что граф не содержит отрицательных весов, тогда можно смело пользоваться Дейкстрой.
"
Он имеет преимущество над скоростью выполнения Беллмана-Форда. Над Дейкстрой имеет преимущество возможностью использования с отрицательными ребрами (ну иногда скоростью тоже, если классик Дейкстра, о чем я писал выше).
Про задачу я уже сказал, думаю, суть уловили. По вашей логике можно дать задачу которая решается одним и только одним алгоритмом, и сказать "вот реши его другим алгоритмом! Не решишь, уложившись в ограниченное время - значит не работает он."
Что ж, я решил еще одну задачу так же 3-мя способами на литкоде. Результаты ниже:
Hidden text
Hidden text
Hidden text
Как видим, мой алгоритм прошел все тесты и по времени не отличается от других известных. НО! Мой то еще с отрицательными весами умеет! Так что делаю, как вы говорите, вывод, что мой алгоритм рабочий.
Пожалуй, обновлю скоро статью, включу туда тесты, исправлю некоторые моменты. Спасибо за задачу, удачи!
Тут немножко поправлю Вас, Дейкстра с кучей работает за O(ElogV)
Полностью согласен, для этой задачи не нужно использовать этот алгоритм.
А что, собственно, не так? Я пояснил этот момент, он никак не влияет на оценку сложности. Или вам смешно от того, что не знакомы с поиском в ширину? Какие злые люди, лишь бы вставить свои 5 грязных копеек. Судя по вашему профилю, вы эти копеечки пытаетесь вставить всюду. Будьте добрее!
Здравствуйте! Спасибо за задачу. Прежде чем обсудить ее, напишу сразу - задачу я решил с моим алгоритмом, но есть нюансы. А теперь к самим нюансам:
После ознакомления с условием задачи я обратил внимание на их тест-кейс:
В их тест-графах присутствуют узлы, у которых 2 разных по весу ребра направлены на один и тот же узел. Т.е. в схеме это выглядит вот так:
От первого узла к третьему 2 ребра разных весов. Я не специалист по графам, поэтому не могу сказать корректен ли этот пример. По моей логике не совсем, но если этому имеет место быть, то ок.
Из первого нюанса следует то, что мне пришлось обрабатывать такие случаи, т.к. в моем алгоритме не предусмотрены такие структуры графов. Мне приходилось записывать в мою структуру графа меньшую из ребер, а поиск меньшего занимало определенное количество ресурсов.
Я пробовал кидать решение на CPython и PyPy. Обратил внимание на то, что там присутствуют тесты с 10^5 узлов и 10^6 ребер. Ограничение 1 сек. Для стандартного питона это ну ооочень тяжко. Для PyPy уже полегче (практически в 2 раза быстрее). Результаты отправки:
Обратите внимание! Ложные ответы отсутствуют (там 23 теста, но у них так же Time Limit). Причем если посмотреть на результаты времени тестов, то можно заметить, что PyPy быстрее примерно в 2 раза. Смотрим на 11 тест. У нас ограничение в 1 сек. Наш тест занял примерно пол секунды на PyPy с верным ответом. А в CPython он вышел за пределы времени (0.5*2=1). Причем код один и тот же. Получается, алгоритм не выдает неверные решения, как вы сказали, а просто выходит за пределы времени. Это не означает что алгоритм не рабочий! Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit (но я не знаю этот язык). Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма), там в условиях отсутствуют ребра с отрицательным весом.
Таким образом, я делаю вывод, что алгоритм работает, но нюансы языка и спорная особенность задачи не позволяют ее сдать в эту систему. Добра Вам!
Hidden text
С этим беда у меня, я не сильный математик, чтобы доказать что-то, поэтому и пишу здесь. Знаю, что обычно доказывают по индукции или "от противного".
Я ради интереса сделал это. Просто вставил счетчик операций в мой цикл и посмотрел на вашем примере графа. Кстати, спасибо за пример, алгоритм чувствует себя похуже других графов. Результат ниже:
В нашем графе мы бы совершили 45 операций, вместо 72 (если судить по формуле).
Кроме того, нашел информацию, что Беллман-Форд имеет наихудшую сложность, которая предполагает ему формула, при линейном графе. Что имею в виду? Представим такого вида линейный граф: 1-->2-->3-->4-->5. Где каждое ребро имеет вес 1. По Беллману-Форду кол-во операций свелось бы как раз к его формуле, а именно 5*4=20. В моем алгоритме:
Т.е. по сути за линию выполнил.
Если я что-то неправильно сделал, может быть, глупость совершил, что в "лоб" посчитал количество операций, то с радостью выслушаю, в чем мой "косяк". Но вроде как взял наихудшие случаи.
Спасибо за пояснения Вам!
Какие "самосортирующиеся списки" вы имеете в виду, поясните, пожалуйста.
В алгоритме операция с множеством осуществляется за константное время, там ничего не перебирается, а лишь проверяется наличие элемента в этом множестве. Напомню, множество в Python реализовано хэш таблицей.
Здесь мне сказать нечего, очень и очень спорное выражение, пожалуй, не буду его развивать.
Про это я уже написал, прочтите, пожалуйста, выше.
Благодарю!
Здравствуйте! Вижу, Вы подкреплены в теме. Сейчас, к сожалению, нет возможности просмотреть и изучить вами присланный материал. Можете, пожалуйста, сказать, правильно ли я оценил сложность (N^2) и какова сложность уже известного алгоритма, о котором Вы упоминаете? Насколько помню, у Беллмана-Форда кубическая сложность, про модификацию его алгоритма я не слышал. Спасибо!
Я не математик, я вообще даже в техническом ВУЗе не учился. А учился я на биолога-химика. В IT сферу ушел, потому что мне с детства нравилась эта тема, но родители хотели, чтобы я был медиком :) В итоге математический бэкграунд у меня хромает. Поэтому и пишу здесь, в надежде найти людей компетентнее. Спасибо!
Хорошо, допустим, включу, но от этого общая сложность не изменится. Поиск в ширину за линейное время выполняется, если граф представлен в корректной структуре данных. Поправьте, если не прав. Спасибо!
Хорошо, буду от вашей структуры отталкиваться. У нас какая задача? Найти кратчайший путь из точки А в точку В. Находим в вашем представлении графа точку А и смотрим на его соседей. Потом находим этих соседей и смотрим их соседей и т.д. Вот это "находим" в вашей беспорядочной структуре будет за N выполняться N раз. Это будет в том случае, если ноды у вас просто беспорядочно расположены в массиве (если вы используете эту структуру данных для хранения). Обычно в программе номер ноды совпадает с номером ячейки в массиве, что позволяет получить к этой ноде доступ за константу. В алгоритме Дейкстры (не я придумал его) как раз таки задача решается именно таким представлением графа, где номер ноды (или буква в лексиграфическом порядке) совпадает с номером ячейки в массиве. То, как вы пытаетесь представить граф - это по сути выстрел себе в ногу. Если отталкиваться от реальной жизни, нужно еще реализовать построение такой структуры графа. Условно ты находишься на перекрестке 1, мне надо в перекресток 10. А дай ка гляну, какие там дороги исходят из перекрестка 7 и запишу. Хотя можно было на второе место записать дороги перекрестка 2. В общем, замечание ваше понятно, но это все общепринятая условность представления данных графа, я это не придумывал.
И все будет работать, в чем подвох? Если вы хотите сделать отрицательный вес графу, который направлен обратно, то это будет отрицательный цикл, а я писал о том, что на таких графах алгоритм не работает (он уйдет в беск. минимизацию веса). На таком графе и дефолтный Беллмана-Форда не будет работать, в чем тогда Ваша претензия. Спасибо!
Согласен, вы хотя бы рассказали, что не так, высказали ваше мнение, спасибо, учту.
Я исправляю эту ситуацию. Подробнее ниже описал. Следим за ситуацией, как говорится :)
Слушайте, если это действительно так, т.е. пока что неработающий алгоритм работает за линейное время, то можно обработать ту проблему, которая ломает алгоритм и тогда сложность будет, если не ошибаюсь, составлять O(n^2). Сейчас есть исправленный код, я его тестирую, если все работает нормально, дополню статью. Становится еще интереснее!
Я описал сложность оригинальной Дейкстры, не совсем понял Вашего исправления. Пояснения в картинке. Источник
Странно, что меня минусуют, ведь я воспринял комментарий так: "Ты питонист, ты не математик! Все питонисты - не математики! Так что не лезь в нашу нишу, программист!" Я и ответил соответствующе, м.б, если обидел, извини, конечно, но и ты меня задел, на самом деле.