Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы. Самому эту фичу прикручивать нужно
С чего вы взяли? Обрабатывают, ещё как. Предварительная обработка не нужна.
Ну попробуйте сами тогда написать на СPython эту задачу. Алгоритмы известные есть, ассимптотика у них известная. Я написал максимально быстрый алгоритм, который знаю, и он все равно не зашел.
Да пожалуйста) Честно признаюсь, что украл этот код, а не написал его сам. Как можете видеть, никакой предобработки графа тут нет.
В одном вы правы - код на с++ эти тесты пролетает со свистом, в разы быстрее питона. Но это лишь очередной повод прекратить кодить на питоне)
import io,os,sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from heapq import *
INF=99**9
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
distances_=[]
for i in range(m):
s,e,w=map(int,input().split())
adj[s-1].append((e,w))
nn=0
pq=[]
heapify(pq)
processed=[0]*n
distances=[INF]*n
distances[nn]=0
heappush(pq,(0,nn+1))
while len(pq) != 0:
searched_distance,searched=heappop(pq)
if processed[searched-1]:
continue
else:
processed[searched-1]=True
for i in adj[searched-1]:
e,w=i[0],i[1]
if searched_distance+w<distances[e-1]:
distances[e-1]=searched_distance+w
heappush(pq,(distances[e-1],e))
distances_.append(distances)
for _ in range(n):
s,e=1,_+1
result=distances_[s-1][e-1]
sys.stdout.write(str(result) + " ")
но ведь изначально посыл поста был в том, что вы изобрели новый алгоритм, который лучше Дейкстры :) ---> Вы точно внимательно читали статью? В каком месте я такое говорил?
Тут недопонимание возникло. Для меня "обычный или классический" Дейкстра - это реализация на куче.
Что ж, я решил еще одну задачу так же 3-мя способами на литкоде. Результаты ниже:
Вас самого ничего не смущает? Алгоритм со сложностью ~n*log(n) отработал за такое же время, как и ~n^2? Точно нет повода задуматься?
Он имеет преимущество над скоростью выполнения Беллмана-Форда.
Но вы не сравнивали его с Беллманом-Фордом) Сравните его с ним, с простейшей оптимизацией "прекратить дальнейшую обработку, если за текущий проход ни один вес не изменился". Может быть очень интересно)
А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще) ---> Как видим, мой алгоритм прошел все тесты и по времени не отличается от других известных. НО! Мой то еще с отрицательными весами умеет! Так что делаю, как вы говорите, вывод, что мой алгоритм рабочий.
Из первого нюанса следует то, что мне пришлось обрабатывать такие случаи - но это ваша проблема) Не стоит заявлять, что в тесткейсах графы какие-то неправильные. Ну и да - в задаче о минимальном пути можно удалить ребра, не потеряв важную инфу. Но в общем случае модифицировать граф не выйдет.
Ложные ответы отсутствуют - а вот это утерждение надо бы подтвердить) там же можно скачать файл с входными данными - запустите локально и посмотрите, что он выдаёт. Наверное, выход лучше писать в файл и сравнивать программно. Если все тесткейсы пройдут - вот тогда можете утверждать, что алгоритм работает верно. Именно поэтому их так много - там как раз задаются разные хитрые графы, которые ломают некорректные алгоритмы, которые "выглядят рабочими". Или рабочие, но слишком медленные) Заодно можете засечь, сколько времени занимает обработка.
Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit - выйдет. Ассимптотика не изменится. Поверьте, если ваш алгоритм вылезает за временные ограничения - 99.9% вероятность в том, что ваш алгоритм имеет неправильную ассимптотику. Только в олимпиадах высокого уровня временные ограничения задаются так, чтобы максимально быстрый алгоритм еле-еле влезал в них. Вот там да, бывают ситуации, когда код на С++ влезет, а его аналог на питоне - нет. Но это не ваш случай.
Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма) - но ведь изначально посыл поста был в том, что вы изобрели новый алгоритм, который лучше Дейкстры :) А выходит, что нет. Вы молодец, что попытались самостоятельно улучшить алгоритм. Но вы не молодец, потому что продолжаете обвинять кого угодно (нюансы языка, спорные особенности задачи...) в том, что ваше решение не проходит. А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще)
Попробуйте сдать эту задачу - https://cses.fi/problemset/task/1671/. Ваша текущая реализация и неправильные ответы выдает, и вываливается за ограничения по времени. Вот когда система засчитает вам задачу - тогда с алгоритмом и приходите)
Привет! Не хочу расстраивать, но у вас не получилось создать собственный алгоритм) И даже модификации Дейкстры не вышло.
Первое - проверка processed ничего не делает. Вы никогда не попытаетесь повторно обработать узел, если у вас не будет дубликатов ключей в хэш-таблице.
Второе - это не Дейкстра, а всего лишь один проход Беллмана-Форда. То, что у вас граф задан матрицей смежности, а не списком рёбер, ничего не меняет. Посмотрите сами - для каждого узла вы рассматриваете все исходящие из него рёбра. После обработки каждого узла вы просмотрите всё рёбра в графе - что и делает Беллман-Форд. Но! - вы это делаете всего один раз, поэтому ваш алгоритм заведомо некорректен.
С чего вы взяли? Обрабатывают, ещё как. Предварительная обработка не нужна.
Да пожалуйста) Честно признаюсь, что украл этот код, а не написал его сам. Как можете видеть, никакой предобработки графа тут нет.
В одном вы правы - код на с++ эти тесты пролетает со свистом, в разы быстрее питона. Но это лишь очередной повод прекратить кодить на питоне)
Тут недопонимание возникло. Для меня "обычный или классический" Дейкстра - это реализация на куче.
Вас самого ничего не смущает? Алгоритм со сложностью ~n*log(n) отработал за такое же время, как и ~n^2? Точно нет повода задуматься?
Но вы не сравнивали его с Беллманом-Фордом) Сравните его с ним, с простейшей оптимизацией "прекратить дальнейшую обработку, если за текущий проход ни один вес не изменился". Может быть очень интересно)
Браво! Потрясающе! Великолепно! Но, к сожалению, ответ на исходный вопрос не был получен. Ознакомьтесь) https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm И никакой предобработки не нужно.
Здравствуйте.
Из первого нюанса следует то, что мне пришлось обрабатывать такие случаи - но это ваша проблема) Не стоит заявлять, что в тесткейсах графы какие-то неправильные. Ну и да - в задаче о минимальном пути можно удалить ребра, не потеряв важную инфу. Но в общем случае модифицировать граф не выйдет.
Ложные ответы отсутствуют - а вот это утерждение надо бы подтвердить) там же можно скачать файл с входными данными - запустите локально и посмотрите, что он выдаёт. Наверное, выход лучше писать в файл и сравнивать программно. Если все тесткейсы пройдут - вот тогда можете утверждать, что алгоритм работает верно. Именно поэтому их так много - там как раз задаются разные хитрые графы, которые ломают некорректные алгоритмы, которые "выглядят рабочими". Или рабочие, но слишком медленные) Заодно можете засечь, сколько времени занимает обработка.
Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit - выйдет. Ассимптотика не изменится. Поверьте, если ваш алгоритм вылезает за временные ограничения - 99.9% вероятность в том, что ваш алгоритм имеет неправильную ассимптотику. Только в олимпиадах высокого уровня временные ограничения задаются так, чтобы максимально быстрый алгоритм еле-еле влезал в них. Вот там да, бывают ситуации, когда код на С++ влезет, а его аналог на питоне - нет. Но это не ваш случай.
Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма) - но ведь изначально посыл поста был в том, что вы изобрели новый алгоритм, который лучше Дейкстры :) А выходит, что нет. Вы молодец, что попытались самостоятельно улучшить алгоритм. Но вы не молодец, потому что продолжаете обвинять кого угодно (нюансы языка, спорные особенности задачи...) в том, что ваше решение не проходит. А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще)
Попробуйте сдать эту задачу - https://cses.fi/problemset/task/1671/. Ваша текущая реализация и неправильные ответы выдает, и вываливается за ограничения по времени. Вот когда система засчитает вам задачу - тогда с алгоритмом и приходите)
Привет! Не хочу расстраивать, но у вас не получилось создать собственный алгоритм) И даже модификации Дейкстры не вышло.
Первое - проверка processed ничего не делает. Вы никогда не попытаетесь повторно обработать узел, если у вас не будет дубликатов ключей в хэш-таблице.
Второе - это не Дейкстра, а всего лишь один проход Беллмана-Форда. То, что у вас граф задан матрицей смежности, а не списком рёбер, ничего не меняет. Посмотрите сами - для каждого узла вы рассматриваете все исходящие из него рёбра. После обработки каждого узла вы просмотрите всё рёбра в графе - что и делает Беллман-Форд. Но! - вы это делаете всего один раз, поэтому ваш алгоритм заведомо некорректен.