Комментарии 108
Поставил минус. Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
Во-первых, эта статья более техническая и качественная чем 80% статей которые мы видели за последние полгода. Работающий код. Рассуждения. Обоснование. Огромные перспективы на развитие еще боле грамотной дискуссии в комментах.
Во-вторых, стэковерфлоу сейчас настолько токсичный (уж насколько мы не любим это слово, но тут только оно) междуусобойчик для олдов, что новичку там появляться страшно. Найти решение там - гуд, задавать вопросы или публиковаться - ну на фиг.
Автора и статью яростно плюсуем:)
Насколько вы уверены в том, что Ваш алгоритм работает?
graph = {
1: {2: 1, 3: 10},
2: {4: 1},
3: {5: 1},
4: {3: 1},
5: {}
}Вот на таком графе он выдает расстояние от 1 до 5, равное 11, при этом существует путь 1->2->4->3->5 длины 4. Условие из пункта "Важно!" вроде как выполнено.
Если ребро ведёт из "нижней вершины" в "верхнюю" и обновляет путь до "верхней" вершины, все пути из "верхней" тоже нужно пересчитывать. Представленный алгоритм это не делает.
Алгоритм Дейкстры этого не делает, потому что он обходит вершины в порядке наименьшей дистанции до исходной, и благодаря отсутствию отрицательных рёбер имеет строгую математическую гарантию, что обновить путь не придётся.
У автора порядок обхода вершин задаётся на входе и если он "правильный" - вершины сразу отсортированы по дистанции от начальной - всё будет работать как надо. Если "неправильный" - как видно по этому тесткейсу, работать не будет.
Спасибо, что привели пример такого вида графа. Я протестировал этот граф, саму цепочку нод он правильно посчитал, но вот с расстоянием да, ошибся. Как вариант, модифицировал код, чтобы он просто проходил по цепочке и обновлял расстояние. Посмотрите еще раз на функцию "get_shortest_path". Костыль, но работает :)
Это математическая задача теории графов - не самой сложной математики и не Pythоn-ом ее решают, а головой!
Так пожалуйста, решайте головой! Берите карту местности вместо смартфона c навигатором и на листочке считайте, как быстрее всего доехать из условной Москвы до Сочи. Уверен, занятие Вам будет по душе :)
Странно, что меня минусуют, ведь я воспринял комментарий так: "Ты питонист, ты не математик! Все питонисты - не математики! Так что не лезь в нашу нишу, программист!" Я и ответил соответствующе, м.б, если обидел, извини, конечно, но и ты меня задел, на самом деле.
Математические задачи решаются головой, на питоне кодятся. Сначала - доказательство, что алгоритм корректный, потом - его реализация. Ну, или тестами обмазывать.
Я не математик, я вообще даже в техническом ВУЗе не учился. А учился я на биолога-химика. В IT сферу ушел, потому что мне с детства нравилась эта тема, но родители хотели, чтобы я был медиком :) В итоге математический бэкграунд у меня хромает. Поэтому и пишу здесь, в надежде найти людей компетентнее. Спасибо!
Позвольте дополнить: математическая задача решается одним из методов ее решения с доказательством; каждый метод генерирует десятки алгоритмов, может сотни; каждый алгоритм может быть запрограммирован тысячами способов, пионтстами, бейсикистами, СИ-иистами, и т.д. В примитивных задачах, часто, метод=алгоритму!
Вы спутали голову с задницей!
А следующий ваш ответ-жалоба ниже лишён логики, что означает: вам не понять алгоритмы! Так что даже, если начнёте с нуля, матрицы и их умножения, а это 9 клас советской школы - бесполезно! Лучше подайте в суд на Российское образование, что утерян ещё один пытливый ум!
Прохождение по соседям узла. Занимает O(E), где Е - количество ребер в графе. Т.к. это константа, то ее опускают.
Это не константа. Максимальное число рёбер зависит от количества узлов. Вы не можете утверждать, чт для любого количества узлов N у графа будет "не более Е рёбер", где Е - константа.
И далее в формуле Вы пишете O(n^2 + E), как будто Вы обходите соседей только для одного, а не для всех узлов.
Более того, максимальное количество рёбер в графе квадратично от количества вершин.
Я описал сложность оригинальной Дейкстры, не совсем понял Вашего исправления. Пояснения в картинке. Источник
Я описал сложность оригинальной Дейкстры, не совсем понял Вашего исправления.
1) В описании сложности алгоритма Дейкстры нигде не написано, что E - это константа и её можно опустить.
2) В оригинальном алгоритме Дейкстры каждое ребро встретится во внутреннем цикле только один раз (для неориентированного графа - 2 раза). Написанное Вами "Мы будем смотреть не минимальный по весу необработанный узел, а смотреть вообще ВСЕХ соседей поочередно" я понял так, что у Вас одно ребро может рассматриваться более одного раза.
IMHO, так гораздо проще:
Для всех узлов записываем длину пути (бесконечность), путь в узел (пусто) и количество родительских узлов.
Создаём очередь узлов для обработки. Помещаем туда стартовый узел,
Пока не дошли до конца очереди.
Выбираем следующий узел из очереди.
Для каждого его дочернего узла.
Если стоимость пути через родительский узел меньше сохранённой, то запоминаем новую стоимость и новый путь.
Уменьшаем счётчик родительских узлов. Если он равен нулю, то добавляем дочерний узел в очередь для обработки.
Восстанавливаем обратный путь из финального узла.
Поставил минус. Статья выглядит примерно так: "мне понравилось изучать алгоритмы, я много интересовался задачей о кратчайших путях и думаю, что мне удалось придумать что-то новое, но в моём окружении нет достаточно компетентных людей, которые бы молги объяснить получилось или нет и почему. Поэтому я напишу статью на хабре и может там мне подскажут". Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
По существу:
* Ваш алгоритм работает за O(E)
* Ваш алгоритм НЕ выдаёт корректные кратчайшие пути
Пример уже писали выше, поделюсь своим
Hidden text
graph = { 1: {2: 20, 3: 30, 4: 10}, 3: {2: 1}, 4: {3: 1} }
--> Минимальные стоимости от источника до ноды: {2: 20, 3: 11, 4: 10}
Если поменять местами описание 3 и 4, то расстояния будут корректными
За алгоритм поиска кратчайших путей, который работает O(E) нобелевскую премию не дадут, а вот премью Тьюринга вполне возможно, правда над этим после Дейкстры/Данцига бьются уже 60 лет, есть почти за O(E), но не совсем (надеюсь коллеги поправят если что).
По уровню материала кажется, что Вам следует разобраться с доказательствами корректности и сложности Дейкстры, Форда-Белламна и Флойда-Уоршела. Если после этого не отпадет желание изучать CS, то вот отличная обзорная презентация от Гольдберга по кратчайшим путям.
Искренне желаю удачи, молодым талантам надо помогать, но и не позволять филонить!
"мне понравилось изучать алгоритмы, я много интересовался задачей о кратчайших путях и думаю, что мне удалось придумать что-то новое, но в моём окружении нет достаточно компетентных людей, которые бы молги объяснить получилось или нет и почему. Поэтому я напишу статью на хабре и может там мне подскажут"
Вы абсолютно правы, я самоучка, у меня нет в окружении ни преподавателей, ни знакомых, кто этим интересуется.
Рвение похвально, но хабр не место для таких статей
А теперь приведу текст политики самого хабра
Считаю, что ставить минус и "хейтить" за то, чем пользуешься по правилам и следуя философии площадки наравне с "моргать дальним и сигналить впереди едущему автомобилю, который едет по ПДД", мол я тут уже не первый год "за рулем", знаю как тут все устроено... В общем, суть уловили, я думаю.
нобелевскую премию не дадут
Здесь, очевидно, была шутка, но если и Вы шутили, то ок
Пример уже писали выше, поделюсь своим
graph = { 1: {2: 20, 3: 30, 4: 10}, 3: {2: 1}, 4: {3: 1} }
--> Минимальные стоимости от источника до ноды: {2: 20, 3: 11, 4: 10}
Если поменять местами описание 3 и 4, то расстояния будут корректными
Не совсем понял, что не так с этим примером? Вы откуда и куда хотите попасть? Если с 1 до 4 ноды, то будет 10, т.е. все правильно.
* Ваш алгоритм работает за O(E)
Вот тут очень спорно, на самом деле, но я не силен в оценивании ассимптотики, поэтому, думаю, коллеги смогут что-то сказать по этому поводу.
Спасибо за фидбэк!
Считаю, что ставить минус и "хейтить"
Я не очень понимаю значения глагола "хейтить", но полагаю, что оно было бы более применимо, если бы я например просто молча поставил минус.
Здесь, очевидно, была шутка, но если и Вы шутили, то ок
Постирония на тему того, что если бы Ваш алгоритм действительно работал, то шутка про нобелевскую премию была бы не такой уж и шуткой.
Не совсем понял, что не так с этим примером? Вы откуда и куда хотите попасть? Если с 1 до 4 ноды, то будет 10, т.е. все правильно.
Расстояние от 1 до 2 это 12 (1->4->3->2), а алгоритм посчитал 20
Вот тут очень спорно
Каждая вершина обрабатывается во внутреннем цикле ровно один раз. Учитывая, что граф обрабатывается списками смежности, то суммарное количество итераций внутреннего цикла -- в точности количество ребер. Если быть более точным, то оценка O(V+E).
Я не очень понимаю значения глагола "хейтить", но полагаю, что оно было бы более применимо, если бы я например просто молча поставил минус.
Согласен, вы хотя бы рассказали, что не так, высказали ваше мнение, спасибо, учту.
Расстояние от 1 до 2 это 12 (1->4->3->2), а алгоритм посчитал 20
Я исправляю эту ситуацию. Подробнее ниже описал. Следим за ситуацией, как говорится :)
Каждая вершина обрабатывается во внутреннем цикле ровно один раз. Учитывая, что граф обрабатывается списками смежности, то суммарное количество итераций внутреннего цикла -- в точности количество ребер. Если быть более точным, то оценка O(V+E).
Слушайте, если это действительно так, т.е. пока что неработающий алгоритм работает за линейное время, то можно обработать ту проблему, которая ломает алгоритм и тогда сложность будет, если не ошибаюсь, составлять O(n^2). Сейчас есть исправленный код, я его тестирую, если все работает нормально, дополню статью. Становится еще интереснее!
Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
Хабр - место в том числе и для таких статей, не нужно тут элитарность вводить.
Поставил минус. Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
Во-первых, эта статья более техническая и качественная чем 80% статей которые мы видели за последние полгода. Работающий код. Рассуждения. Обоснование. Огромные перспективы на развитие еще боле грамотной дискуссии в комментах.
Во-вторых, стэковерфлоу сейчас настолько токсичный (уж насколько мы не любим это слово, но тут только оно) междуусобойчик для олдов, что новичку там появляться страшно. Найти решение там - гуд, задавать вопросы или публиковаться - ну на фиг.
Автора и статью яростно плюсуем:)
Спасибо за добрую оценку!
Ironic.
Буквально на днях с коллегами спорил, слышал от них ровно обратное - что на stackoverflow соваться не страшно: там помогут не создавая ощущения, что ты - тварь ничтожная, а вот от хабра или тем более ЛОРа такое ощущение есть. По тону статьи хорошо заметно, что автору хочется фидбека, но он боится разгрома в комментах и/или минусов в карму. Это вполне можно рассматривать как признак не очень здоровой среды. А можно и не рассматривать.
Рискну предположить, что дело в индивидуальной чувствительности и предпочтениях в обучении. Ну и, конечно, совсем разный формат.
там помогут не создавая ощущения, что ты - тварь ничтожная
Если спросить в стопицотый раз, как отцентрировать див внутри дива, то помогут: вопрос закроют, а тебе дадут ссылку на предыдущий, раз сам искать не умеешь.
А спроси, как писать оптимальные по производительности селекторы и стили, так сразу «ненастоящий вопрос».
А ещё как-то я постил вопрос про CSS, сопроводив его для иллюстрации разметкой на кастомном языке (диалект HTML, абсолютно очевидный), которую тупо скопировал из проекта. И хотя вопрос касался строго CSS, а разметка была приведена для пущей понятности, ни одна тварь не ответила про CSS, зато около десяти тварей сочло своим долгом написать, что я не умею в HTML. После пояснений, что это код не для браузера, вопрос закрыли как ненастоящий (!!!).
Это нормально и абсолютно предсказуемо, потому что приход таков, каков поп, а основатели, в первую очередь дядя Джоэл, показали себя, введя изменения правил спустя годы после открытия проекта, и удалив дохренищща полезного контента, который висел у меня в закладках. Надо быть настоящим говнюком, чтобы придавать законам обратную силу без очень веских причин.
Согласен с вашими коллегами.
Я тоже заступлюсь за автора. Среди множества последних статей, к этой статье меньше всего вопросов что она делает на хабре. Более того как уже поясняли, хабр это то место где можно получить хорошую обратную связь (я сам этим пользуюсь и буду пользоваться), и поэтому я считаю что нужно таких статей еще больше. поэтому статье и автору плюс однозначный. И вам плюс за за то что делаете хабр тоже лучше) В отличие от других минусаторов, вы хотя бы даете обратную связь, аргументируете, даете полезные советы.
Поставил вам минус за элитарность. Из-за вас хабр и превратился в помойку с "новостями"
А каким образом? Я изредко пишу технические статьи в области где хорошо разбираюсь, дал развернутый комментарий автору по поводу фундаментальных технических проблем статьи.
Вы пришли и сказали, что я хам, поэтому поставите мне минус, не дав при этом ни автору, ни комьюнити никакой полезной информации по теме.
А точно из-за меня хабр помойкой с новостями?
Мне кажется, что одна из крупных и давних проблем Хабра -- снобизм. О чём автор и написал.
Ещё одна -- двойные стандарты. Когда похают Россию -- норм. Если только отпустишь сарказм про США, то карму занизят, что даже и лайки не работают. ))
Демократия... ))
Мне, лично, кажется, что не стоит самодельным авторам так бить по рукам.
Пусть пишут. Рейтинг статьи сам по себе должен регулировать этот вопрос: показы, рейтинг автора, в конечном итоге и пр.
Иначе, получится, как в Википедии, где, вроде, как народное голосование по всем вопросам, но...
Если добавляешь данные о применении кассетного минирования жилых кварталов на востоке самостийной, то бан. А если рассказать без ссылок и доказательств про Бучу, то медали выдают.
Надо тоньше работать. И давать дорогу молодым.
У вас в статье собственно три основные проблемы:
"Нужно писать узлы графа в порядке их отдаленности от источника. Т.е.
сперва описываем первых соседей источника. После того, как описали их,
приступаем к следующим соседям соседей."
Таким образом вы решаете не известную задачу, а какую-то другую. Соответственно, чтобы получить честные оценки асимптотики, нужно добавить этот этап препроцессинга
Сложность Дейкстры при нормальной реализации, это "Dijkstra's algorithm with Fibonacci heap O ( E + V log V )", или "Dijkstra's algorithm with binary heap O ( ( E + V ) log V)" https://en.wikipedia.org/wiki/Shortest_path_problem (то есть фактически близко к линейному)
Ваш алгоритм не работоспособен для негативных и положительных весов в общем случаи, то есть не является аналогом Bellman–Ford.
А каким образом Вы представляете граф во входную точку программы? Произвольные ноды и описание их соседей? Насколько помню, даже та же матрица смежностей реализует представление графа "по порядку". Даже возьмем ту же карту и текущую геопозицию. На вход программе уже будет произведен поиск в ширину и все будет по порядку. Не представляю, как можно подать на вход описание нод в разнобой, м.б. имеет место быть где-то, но это можно обработать в коде, поэтому, возможно Вы и правы насчет сложности.
Я об этом написал вообще-то, что сложность с реализацией приоритетной очереди будет такая, но она не всегда будет такой, в редких случаях "быстрее будет медленный алгоритм", как бы тавтологически не звучало.
Аргументируйте, пожалуйста. Приведите пример графа и разберемся вместе. По существу, это пальцем в небо тыкнули.
Не надо пожалуйста издеваться над здравым смыслом. Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено. Не говоря уже о различных представлениях в виде матриц смежности.
3. Замените половину весов на отрицательные и посмотрите, что там посчитается.
Определение графа знаете? Набор вершин и дуг, в котором дуги являются парами связных вершин, плюсом веса для дуг в нашем случаи. Никакого порядка там в принципе не предусмотрено.
Хорошо, буду от вашей структуры отталкиваться. У нас какая задача? Найти кратчайший путь из точки А в точку В. Находим в вашем представлении графа точку А и смотрим на его соседей. Потом находим этих соседей и смотрим их соседей и т.д. Вот это "находим" в вашей беспорядочной структуре будет за N выполняться N раз. Это будет в том случае, если ноды у вас просто беспорядочно расположены в массиве (если вы используете эту структуру данных для хранения). Обычно в программе номер ноды совпадает с номером ячейки в массиве, что позволяет получить к этой ноде доступ за константу. В алгоритме Дейкстры (не я придумал его) как раз таки задача решается именно таким представлением графа, где номер ноды (или буква в лексиграфическом порядке) совпадает с номером ячейки в массиве. То, как вы пытаетесь представить граф - это по сути выстрел себе в ногу. Если отталкиваться от реальной жизни, нужно еще реализовать построение такой структуры графа. Условно ты находишься на перекрестке 1, мне надо в перекресток 10. А дай ка гляну, какие там дороги исходят из перекрестка 7 и запишу. Хотя можно было на второе место записать дороги перекрестка 2. В общем, замечание ваше понятно, но это все общепринятая условность представления данных графа, я это не придумывал.
Замените половину весов на отрицательные и посмотрите, что там посчитается.
И все будет работать, в чем подвох? Если вы хотите сделать отрицательный вес графу, который направлен обратно, то это будет отрицательный цикл, а я писал о том, что на таких графах алгоритм не работает (он уйдет в беск. минимизацию веса). На таком графе и дефолтный Беллмана-Форда не будет работать, в чем тогда Ваша претензия. Спасибо!
Если что, есть три классических представления графа - списки вершин и рёбер, матрица смежности, список смежности. Нигде не гарантируется упорядоченность. Это часть задачи.
Пользуясь примером с картой, пусть на входе есть список городов в алфавитном порядке. В том же порядке даны соответствующие рёбра графа. Где-то в самом начале "пути" от Владивостока до Хабаровска встретятся Владикавказ, Воркута и Выборг. Решением задачи мы, собственно, пытаемся навести порядок в структуре, сотворённой без учёта взаимного расположения городов и доступности транспорта. Так понятнее?
"На входе будет произведён поиск в ширину" - тогда включайте в алгоритм. Тоже путь.
тогда включайте в алгоритм
Хорошо, допустим, включу, но от этого общая сложность не изменится. Поиск в ширину за линейное время выполняется, если граф представлен в корректной структуре данных. Поправьте, если не прав. Спасибо!
Всё так, но именно поэтому этому утверждению самое место в исходном обосновании ;) Так сразу можно сказать, что если кто не по фэншую принёс данные, то ещё E log E набежит на сортировку рёбер графа, например.
Да, и ещё - сложность для обхода графов обычно выражают как функцию количества рёбер и количества вершин, не пренебрегая ни одной из компонент. А то вдруг решите натравить алгоритм на полные графы, и тут-то выяснится, что O(E) - это O(N^2). А может быть, ближе к O(N). В общем, в таком представлении полезнее выходит.
Хорошая статья, делай еще! Идея неплохая!
Чёт я не понял зачем новый алгоритм. Разве нельзя ко всем весам прибавить 4 и свести задачу к неотрицательным весам?
Тоже такое первое приходит в голову, когда вижу граф с отрицательными весами.
Нельзя.
Возьмём граф (AB: -2, BC: 2, AС: 1). Очевидно, что путь ABC со стоимостью 0 выгоднее, чем AC со стоимостью 1.
Теперь добавим 2 ко всем рёбрам, чтобы избавиться от отрицательной стоимости. Получим граф (AB: 0, BC: 4, AC: 3). Путь ABC теперь имеет стоимость 4, а путь AC стоимость 3, что явно не соответствует исходному графу.
В общем, ваша "добавка" будет входить в путь столько раз, сколько рёбер на этом пути.
И, соответственно, чем больше рёбер имеет путь, тем большая стоимость к нему добавится.
Если бы всё было так просто, то можно было бы в конце расчетов вычесть эту добавку столько раз, сколько ребер в итоговом пути получилось. Подозреваю, что при этом сломается динамическое программирование при обходе вершин.
Обязательно сломается.
Классический алгоритм Дейкстры это модификация волнового алгоритма. Если представить, что волна распространяется по графу с фиксированной скоростью, а веса рёбер - это длины пути, то фактически минимальная стоимость пути до определённого узла - это время прихода в него волны. Отрицательные стоимости рёбер, как и вычитание добавки, отправляют волну в прошлое и она может прийти в уже обработанный алгоритмом узел, а повторная обработка узлов алгоритмом Дейкстры не предусмотрена.
Контрпример, пользуясь терминологией автора:
graph = {
1: {2: -4, 3: 7}
2: {3: 10}
3: {}
}Проблема в том, что прибавляемая сумма зависит от длины пути.
1 -> 2 -> 3 (два ребра)
1 -> 3 (одно ребро)
Возможно, автору понравится алгоритм Джонсона и алгоритм Дейкстра с Фибоначчиевой кучей. Можно посмотреть лекции МФТИ авторства Филиппа Руховича. Там есть довольно интересные алгоритмы, сложность которых довольно неплохая, если выполнены некоторые хитрые соотношения на V и E.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Джонсона
https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча
https://youtu.be/zeB-DgV53d0?si=ZjF1oBvWHoQlsqjw
Если дать этой программе на вход вершины в том порядке, в котором они идут в искомом кратчайшем пути -- то она вероятно его найдёт. Проблема в том, что у порядка обхода в ширину такого свойства нет, так что вы просто спрятали сложность алгоритма в этот препроцессинг. Выше уже приводили несколько контрпримеров, даже без отрицательных весов, я приведу версию, в которой parents тоже считается некорректно:
Hidden text
graph = {
1: {2: 1, 3: 20, 5: 10},
2: {4: 1},
3: {5: 1},
5: {},
4: {3: 1},
}
# 1 ---
# / \ \
# 2 3 - 5
# | /
# 4
# outputs:
costs = {2: 1, 3: 3, 5: 10, 4: 2}
parents = {2: 1, 3: 4, 5: 1, 4: 2}
# на самом деле должно быть parents[5] == 3 и costs[5] == 4
# (1 -> 2 -> 4 -> 3 -> 5)Вся программа работает за O(V + E) (если доступ ко всем использованным питоновским структурам данных работает за (амортизационное) O(1), но это вроде правда), так как внутренний цикл проходится по всем рёбрам по 1 разу, а внешний -- по всем вершинам, и это оптимальное время, за которое можно из правильно отсортированного списка вершин получить кратчайшие расстояния, но сама сортировка займёт больше времени.
Ещё не совсем понял, зачем вам нужен processed , как будто бы в него просто переписываются все пройденные вершины, которые и так обрабатываются ровно 1 раз, поскольку внешний цикл проходится по ним ровно 1 раз
Не очень полезно с существованием SPFA
Необходимо более строгое доказательство и оценки/проверки на случайных графах, например модели Эрдеша-Реньи
Привет! Не хочу расстраивать, но у вас не получилось создать собственный алгоритм) И даже модификации Дейкстры не вышло.
Первое - проверка processed ничего не делает. Вы никогда не попытаетесь повторно обработать узел, если у вас не будет дубликатов ключей в хэш-таблице.
Второе - это не Дейкстра, а всего лишь один проход Беллмана-Форда. То, что у вас граф задан матрицей смежности, а не списком рёбер, ничего не меняет. Посмотрите сами - для каждого узла вы рассматриваете все исходящие из него рёбра. После обработки каждого узла вы просмотрите всё рёбра в графе - что и делает Беллман-Форд. Но! - вы это делаете всего один раз, поэтому ваш алгоритм заведомо некорректен.
Недопонимание основано на том, что автор ищет путь в ориентированном графе, что является тривиальным алгоритмом. В свою очередь, алгоритмы Дейкстры и Форда-Беллмана без проблем работают на неориентированных графах.
Если рассмотреть работу данного алгоритма на неориентированном графе, то сразу возникнут проблемы:
Проблема 1. Неправильная ориентация ребра на этапе препроцессинга (этап, который автор решил опустить в посте).
Фраза "Нужно писать узлы графа в порядке их отдаленности от источника" крайне расплывчата и, если я правильно понял, может привести, например, к такому:
Дано: Неориентированный граф с 5-ю вершинами
Ребра: (1, 2), (1, 3), (2, 5), (2, 6), (3, 4), (4, 5)
Найти кратчайший путь от 1 до 6
Порядок "отдалености" от начальной вершины может быть таким, что ребра ориентируются так:
1 -> 2, 1 -> 3, 2 -> 5, 2 -> 6, 3 -> 4, 4 -> 5
Как видно, в изначальном неориентированном графе есть путь 1 -> 3 -> 4 -> 5 -> 2 -> 6. В измененном ориентированном графе такого пути нет (нет ребра 5 -> 2). Если этот путь самый короткий, то алгоритм его не найдет.
Проблема 2. Проблема возникает только если закрыть глаза на первую проблему и остальные шероховатости алгоритма, которые разобраны в других комментариях, но всё же я опишу и её.
Можно подвесить неориентированный граф за начальную вершину так, чтобы проблемы 1 не возникло. Но в таком случае алгоритм находит (не без доработок) расстояние (и путь) только от одной конкретно заданной вершины до другой конкретно заданной вершины. Напомню, что, например, Дейкстра находит от одной до всех остальных.
Дабы не быть голословным:
Дано: Неориентированный граф с 4-мя вершинами
Ребра: (1, 2), (1, 3), (2, 4), (3, 4)
Веса: (1, 2) -> 10, остальные по 1
Найти кратчайший путь от 1 до 4
Ориентируем граф: 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4 (учли все возможные пути из вершины 1 в вершину 4)
Кратчайший путь найден: 1 -> 3 -> 4 (вес: 2)
Какой же за кратчайший путь от вершины 1 до вершины 2? Согласно алгоритму 1 -> 2 (вес: 10). Верный же ответ: 1 -> 3 -> 4 -> 2 (вес: 3)
P.S. Автору шлю лучи поддержки! Посту поставил плюс, ведь главное разобраться, а не устраивать срач.
> автор ищет путь в ориентированном графе, что является тривиальным алгоритмом
Неориентированный граф - частный случай ориентированного, проблема не в этом. Проблема в том, что автор ищет путь в ациклическом графе.
И ациклический граф мы действительно можем топологически отсортировать и рассчитать расстояния от одной вершины до всех за O(N+E)
А вообще, как заметили выше, это практически действительно один шаг Форда-Беллмана. Но вершины ациклического графа как раз можно обрабатывать в порядке топологической сортировки, и при этом одного шага достаточно.
это не справедливо требовать предупорядоченности графа под исходную точку, и не учитывать сложность предупорядочивания. Обычно граф задан заранее. Например - граф дорог. Ширина дорог, наличие поворотов, светофоров, переходов и пр. учитваются в виде весов. Сейчас нужно посчитать лучший машрут из точки А в Z, а через секунду для другого пользователя из K в G. И значит надо постоянно предупорядочивать чтобы ваш алгоритм работал. Я правильно понимаю суть важных ограничений?
Самообман в оценке сложности алгоритма виден невооруженным взглядом. Она связана с непониманием вычислительной сложности используемых программных конструктов (и показывает, почему Python не считается приемлемым для обучения базовым методам программирования) - очень многие действия кажутся "бесплатными". Например, использование множеств и самосортирующихся списков - да-да, это всё тоже считается в оценке сложности.
А в остальном алгоритм - просто немного кривая реализация Дейкстры, но не в варианте "оптимально растущей границы" (традиционный метод), а комбинация поиска в ширину с поиском в глубину. Причем с апостериорной оценкой удаленности узлов. За счет ... хм, "бесплатного" множества, которое, как бы "сразу знает", а не перебирает всё, что в него накидано, при каждом запросе.
И вот что ещё важно. Реальный граф, по которому ищется путь - это тысячи узлов и, часто, намного больше. В таких ситуациях любое "оптимизация" вроде сортировок всех узлов - огромная вычислительная нагрузка.
использование множеств и самосортирующихся списков - да-да, это всё тоже считается в оценке сложности
Какие "самосортирующиеся списки" вы имеете в виду, поясните, пожалуйста.
За счет ... хм, "бесплатного" множества, которое, как бы "сразу знает", а не перебирает всё, что в него накидано, при каждом запросе
В алгоритме операция с множеством осуществляется за константное время, там ничего не перебирается, а лишь проверяется наличие элемента в этом множестве. Напомню, множество в Python реализовано хэш таблицей.
Python не считается приемлемым для обучения базовым методам программирования
Здесь мне сказать нечего, очень и очень спорное выражение, пожалуй, не буду его развивать.
И вот что ещё важно. Реальный граф, по которому ищется путь - это тысячи узлов и, часто, намного больше. В таких ситуациях любое "оптимизация" вроде сортировок всех узлов - огромная вычислительная нагрузка.
Про это я уже написал, прочтите, пожалуйста, выше.
Благодарю!
1
Комментарий по алгоритму в update 2.
Я не готов ручаться за мелкие баги, но в целом ваш алгоритм должен работать, так как Вы переизобрели алгоритм Форда-Беллмана с реализацией на очереди, можно про это почитать вот тут
https://acm.math.spbu.ru/~sk1/courses/1718s_au/conspect/conspect.pdf
https://algs4.cs.princeton.edu/44sp/
Также стоит отметить, что по форме алгоритм очень схож со scanning method (его кстати тоже Форд придумал), который является общим видом для большинства известных алгоритмов поиска кратчайшего пути, различающихся лишь тем как выбирать очередную вершину из lst. При выборе наименьшей по расстоянию получается Дейкстра, при выборе в порядке обычной очереди получается Форд-Беллман. Про этот метод можно прочитать в том числе в презентации Гольдберга, ссылку на которую я уже присылал
Здравствуйте! Вижу, Вы подкреплены в теме. Сейчас, к сожалению, нет возможности просмотреть и изучить вами присланный материал. Можете, пожалуйста, сказать, правильно ли я оценил сложность (N^2) и какова сложность уже известного алгоритма, о котором Вы упоминаете? Насколько помню, у Беллмана-Форда кубическая сложность, про модификацию его алгоритма я не слышал. Спасибо!
@wataruв соседней ветке написал, что сложность у Форда-Беллмана O(VE) и пример хороший привел где, к сожалению, отдельные оптимизации его асимптотически не ускоряют (т.е. оптимизации работают, алгоритм отрабатывает быстрее, но это все еще O(VE) с меньшей константой).
Сейчас, к сожалению, нет возможности просмотреть и изучить вами присланный материал.
Ну .... Вы сами сделали выбор попробовать допилить алгоритм вместо того, чтобы изучить материал ;)
Вообще, что касается алгоритмов, то тут по умолчанию надо считать, что он не работает, пока не доказано обратное. Надо математически доказать, что найдутся кратчайшие пути. Ввести какие-то инварианты, вроде "до вершин в обработанном множестве найдены кратчайшие пути". Показать, почему он поддерживается.
Главная проблема вашего алгоритма - он работает по слоям. Однако кратчайший путь может состоять из огромного количества коротких ребер и идти задом-на-перед по слоям. Сама идея этого расслоения графа принципиально не работает.
Что касается заплатки в upd2, то у вас там получился в итоге форд беллман, только сильно накрученный. По крайней мере, сложность точно такая же: O(VE). Ибо каждая вершина может быть в очереди на обработку до O(V) раз.
Вот тест:
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},
}Это линия из треугольников, где выгоднее брать два ребра вместо одного. Если подсчитать, сколько раз вершины будут обработаны и вывести - там будет номер треугольника +-1. Так что в среднем будет O(n) на каждую вершину. Тут ребер не много, но можно граф усложнить.
Надо математически доказать, что найдутся кратчайшие пути. Ввести какие-то инварианты, вроде "до вершин в обработанном множестве найдены кратчайшие пути". Показать, почему он поддерживается.
С этим беда у меня, я не сильный математик, чтобы доказать что-то, поэтому и пишу здесь. Знаю, что обычно доказывают по индукции или "от противного".
Если подсчитать, сколько раз вершины будут обработаны и вывести
Я ради интереса сделал это. Просто вставил счетчик операций в мой цикл и посмотрел на вашем примере графа. Кстати, спасибо за пример, алгоритм чувствует себя похуже других графов. Результат ниже:
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. В моем алгоритме:
graph = {
1: {2:1},
2: {3:1},
3: {4:1},
4: {5:1},
5: {},
}
# -> Количество операций: 4Т.е. по сути за линию выполнил.
Если я что-то неправильно сделал, может быть, глупость совершил, что в "лоб" посчитал количество операций, то с радостью выслушаю, в чем мой "косяк". Но вроде как взял наихудшие случаи.
Спасибо за пояснения Вам!
"Важно! Нужно писать узлы графа в порядке их отдаленности от источника. "
скажите - мне одному смешно или кто то ещо хихикает с такого "поиска" кратчайшего пути
А что, собственно, не так? Я пояснил этот момент, он никак не влияет на оценку сложности. Или вам смешно от того, что не знакомы с поиском в ширину? Какие злые люди, лишь бы вставить свои 5 грязных копеек. Судя по вашему профилю, вы эти копеечки пытаетесь вставить всюду. Будьте добрее!
Или вам смешно от того, что не знакомы с поиском в ширину?
Под "отдалённостью от источника" Вы, видимо, подразумеваете расстояние в штуках (рёбрах). Но догадаться об этом - нетривиальная задача. Во взвешенном графе принято расстояние считать в весах. И поэтому задача на первый взгляд звучит так: найти кратчайшее расстояние до узла, но все узлы должны быть отсортированы по расстоянию".
Какие злые люди, лишь бы вставить свои 5 грязных копеек.
Вы ранее, ссылаясь на политику Хабра, написали, что опубликовали свою статью, чтобы более опытные товарищи указали Вам на Ваши ошибки. При этом, любое указание на ошибки Вы воспринимаете очень агрессивно. Прежде чем огрызаться, стоило бы задумываться, почему Вам так написали.
p.s. Телепаты в отпуске.
Тебе одному. Существует достаточное количество алгоритмов, которым требуется предобработка данных. Полистай КМП для примеров.
Попробуйте сдать эту задачу - https://cses.fi/problemset/task/1671/. Ваша текущая реализация и неправильные ответы выдает, и вываливается за ограничения по времени. Вот когда система засчитает вам задачу - тогда с алгоритмом и приходите)
Здравствуйте! Спасибо за задачу. Прежде чем обсудить ее, напишу сразу - задачу я решил с моим алгоритмом, но есть нюансы. А теперь к самим нюансам:
После ознакомления с условием задачи я обратил внимание на их тест-кейс:
В их тест-графах присутствуют узлы, у которых 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
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=' ')
Проблема не только в языке. Ваш метод работает за O(VE), когда как дейкстара работает за O(V+E). Ваш метод даже на С++ не зайдет по ограничению времени (10^(5+6) - 100 миллиардов операций вы в 1 сек ну никак не запихнете). Правда, ваш метод работает и с отрицательными ребрами, когда как в этой задаче их нет, поэтому она рассчитана на более простой и быстрый алгоритм.
когда как дейкстара работает за O(V+E)
Тут немножко поправлю Вас, Дейкстра с кучей работает за O(ElogV)
Правда, ваш метод работает и с отрицательными ребрами, когда как в этой задаче их нет, поэтому она рассчитана на более простой и быстрый алгоритм.
Полностью согласен, для этой задачи не нужно использовать этот алгоритм.
Здравствуйте.
Из первого нюанса следует то, что мне пришлось обрабатывать такие случаи - но это ваша проблема) Не стоит заявлять, что в тесткейсах графы какие-то неправильные. Ну и да - в задаче о минимальном пути можно удалить ребра, не потеряв важную инфу. Но в общем случае модифицировать граф не выйдет.
Ложные ответы отсутствуют - а вот это утерждение надо бы подтвердить) там же можно скачать файл с входными данными - запустите локально и посмотрите, что он выдаёт. Наверное, выход лучше писать в файл и сравнивать программно. Если все тесткейсы пройдут - вот тогда можете утверждать, что алгоритм работает верно. Именно поэтому их так много - там как раз задаются разные хитрые графы, которые ломают некорректные алгоритмы, которые "выглядят рабочими". Или рабочие, но слишком медленные) Заодно можете засечь, сколько времени занимает обработка.
Если этот же алгоритм написать на C++, то он скорее всего не выйдет за time limit - выйдет. Ассимптотика не изменится. Поверьте, если ваш алгоритм вылезает за временные ограничения - 99.9% вероятность в том, что ваш алгоритм имеет неправильную ассимптотику. Только в олимпиадах высокого уровня временные ограничения задаются так, чтобы максимально быстрый алгоритм еле-еле влезал в них. Вот там да, бывают ситуации, когда код на С++ влезет, а его аналог на питоне - нет. Но это не ваш случай.
Плюс ко всему эту задачу нужно решать обычной Дейкстрой (который в любом случае быстрее моего алгоритма) - но ведь изначально посыл поста был в том, что вы изобрели новый алгоритм, который лучше Дейкстры :) А выходит, что нет. Вы молодец, что попытались самостоятельно улучшить алгоритм. Но вы не молодец, потому что продолжаете обвинять кого угодно (нюансы языка, спорные особенности задачи...) в том, что ваше решение не проходит. А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще)
Не стоит заявлять, что в тесткейсах графы какие-то неправильные.
Ок. Проверил информацию в интернете, такие графы существуют, но называются они мультиграфами. Мой же алгоритм в исходном исполнении рассчитан на простые графы. Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы. Самому эту фичу прикручивать нужно. Но да ладно не совсем проблема это.
Ложные ответы отсутствуют - а вот это утерждение надо бы подтвердить)
Я не поленился и сделал это. И знаете что? Все тесты пройдены! Результаты можете сами проверить, там сам код, время выполнения и правильность ответа. Я сравнивал мой алгоритм с классическим алгоритмом Дейкстры и с Дейкстрой, реализованном на куче. Запускал на процессоре 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 млрд операций.
Видим, что для этой задачи мой алгоритм не подходит! Более того, не подходит и классическая Дейкстра. И даже, в некоторых тестах Дейкстра с кучей тоже не зашла! Плюс там дополнительное время уходит на обработку мультиграфа. Тесты все алгоритмы проходят долго, а иногда очень долго. Но если заметить, в среднем мой алгоритм даже чуточку быстрее прошел, чем классик Дейкстра (бывало и сильно медленнее, но реже). Так что, эвристическая сложность, считаю, все равно не плохой.
Если этот же алгоритм написать на 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_distanceHidden 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_valHidden 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)Как видим, мой алгоритм прошел все тесты и по времени не отличается от других известных. НО! Мой то еще с отрицательными весами умеет! Так что делаю, как вы говорите, вывод, что мой алгоритм рабочий.
Пожалуй, обновлю скоро статью, включу туда тесты, исправлю некоторые моменты. Спасибо за задачу, удачи!
Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы
Вообще говоря, обрабатывают. Да и ваш алгоритм бы обрабатывал элементарно, надо лишь формат хранения графа заменить со словаря словарей на словарь списков (куда ведет ребро и какой оно длины).
Вообще говоря, обрабатывают.
Да, пардон, виноват, обрабатывают. Я просто привык к своей структуре графа, что забыл уже, что в других алгоритмах она другая и там он просто в процессе выполнения алгоритма сам по себе выберет меньшую из ребер. Но стоимость операций от этого не снизится, т.к. по сути это будет такой же лишний проход, как и "оставления" меньшего ребра в моей реализации.
формат хранения графа заменить со словаря словарей на словарь списков (куда ведет ребро и какой оно длины)
В моем алгоритме это приведет либо к росту сложности, либо к росту памяти. Поясню, смотрите, если сделать, как вы предлагаете, тогда придется изменять функцию построения кратчайшего пути:
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 элементов. Ухудшение по памяти.
Вывод: с мультиграфами в любом случае немножко похуже, чем с простыми графами. Мое решение этой проблемы вполне себе рабочее, я считаю. Возможно, даже и дешевле, нежели у Дейкстры и Беллмана-Форда.
просто привык к своей структуре графа, что забыл уже, что в других алгоритмах она другая
В большинстве алгоритмов структура графа вообще не записана. Там что-нибудь вроде "обойти все ребра из вот этой вот вершины".
Но стоимость операций от этого не снизится, т.к. по сути это будет такой же лишний проход, как и "оставления" меньшего ребра в моей реализации.
Просто эта стоимость уже учтена в ассимптотике. Вот это вот E в каком-нибудь O(VE) алгоритма Форда-Беллмана - это общее количество ребер. Считая петли и параллельные ребра.
В моем алгоритме это приведет либо к росту сложности, либо к росту памяти
Я имел ввиду хранить список ребер в виде:
graph = {1: [[2, 100], [3, 10]]} // ребра 1->2 (длина 100) и 1->3 (длина 10))Вам же в алгоритме не надо брать ребро между двумя заданными вершинами. Вы там всегда проходитесь по всем ребрам из текущей, что в такой структуре делается нисколько ни медленнее. Вы там у себя в алгоритме вызываете .items() у графа, что по-сути итак возвращает именно такой же список из списков. Ну touples там может быть не принципиально. Один фиг вы там словарь как словарь не используете.
В моем алгоритме это приведет либо к росту сложности, либо к росту памяти.
Оно лишь увеличит то самое E - количество ребер. Которое в вашем алгоритме входит в сложность O(VE). Да, на графе с кучей параллельных ребер ваш алгоритм будет работать дольше и потребует больше памяти. Но не потому, что параллельные ребра какие-то особенные, а потому что там ребер больше. Точно так же как и в почти полном графе ваш алгоритм будет требовать больше памяти и времени, чем в почти дереве (как и большинство других алгоритмов).
Если список инициализировать количеством узлов, чтобы за константу получить вторую ноду, тогда у нас было бы n списков из n элементов.
Вообще, ваша идея иметь изначальный список всех вершин в порядке удаления - весьма странная. Надо туда запихать лишь начальную вершину и все. Вы итак изменили алгоритм в Upd2 тем, что вы добавляете вершины вы список на обработку. Вот у вас так получается очередь обхода в ширину и список сам создасться в процессе работы алгоритма.
Я имел ввиду хранить список ребер в виде:
Да, я так и понял, что такой вид примет структура.
Вам же в алгоритме не надо брать ребро между двумя заданными вершинами.
Когда проходишь по всем ребрам в первой части алгоритма, то да. Но когда вычисляешь расстояние, мне как раз-таки это и нужно! Я вам специально прислал кусок кода, где мне это нужно, посмотрите внимательнее.
Да, на графе с кучей параллельных ребер ваш алгоритм будет работать дольше и потребует больше памяти. Но не потому, что параллельные ребра какие-то особенные, а потому что там ребер больше.
Смотрите, заранее удалить ребро в моей реализации будет дешевле, чем обрабатывать его более тяжелой операцией. Поэтому идея не самая плохая. По сравнению с известными алгоритмами уже быстрее будет по идее. Это будут "не одинаковые" EV. Там E уже по сути будет меньше.
Вообще, ваша идея иметь изначальный список всех вершин в порядке удаления - весьма странная.
Повторюсь, прочитайте еще раз статью, пожалуйста. Чувствую, вы суть не до конца поняли. Без этого списка я бы не построил свою структуру графа. В той же Дейкстре если создается матрица смежностей, то это двумерный список, где i-ый элемент соответствует i-му узлу. Поэтому если вы говорите, что это идея странная, то значит и у известных алгоритмов она тоже странная. Впрочем, я писал об этом, можете ознакомиться еще раз.
Но когда вычисляешь расстояние, мне как раз-таки это и нужно!
Ах, вы про восстановление пути. Ну так это лечится элементарно: Вы в каждой вершине уже храните предыдущую в кратчайшем пути. Так вы путь восстановите. А вот длина пути у вас уже подсчитана в costs[end]. Вам не надо в восстановлении пути все ребра еще раз суммировать.
Смотрите, заранее удалить ребро в моей реализации будет дешевле, чем обрабатывать его более тяжелой операцией.
Ну да, ваш алгоритм от такой оптимизации выиграет, согласен.
Без этого списка я бы не построил свою структуру графа
Вам в алгоритме нужно 2 вещи: список смежных ребер к каждой вершине и ваш список вершин в порядке удаления от изначальной (по ребрам). Список ребер можно хранить как угодно, лишь бы вы могли все ребра от одной вершины перебрать. Список вершин, ваш lst строится обходом в ширину. Вы его изначально запоняете всеми вершинами в известном порядке. Он вам действительно нужен до upd2. Но после этот же самый список построится сам, вы ведь в lst добавляете вершины, до которых находите лучшее расстояние! Фактически как в bfs. Попробуйте ваш код изменить - делайте lst = {1}, и вы водите в каком порядке у вас вершины обрабатываются - будет точно такой же порядок почти на всех графах. А там где порядок будет другой, потому что вершины по куче раз в список добавляются, ну так этот порядок даже более верный будет, ведь почему вы уже обработанную вершину добавляете в конец очерди, после всех вершин графа? Вдруг у вас там в графе какие-то вершины вообще с начальной не связаны, зачем их обрабатывать раньше тех, до которых вы уже дошли?
Доброе утро! У меня статья обновлена, я ускорил момент с lst, взгляните еще раз. Что касается предложения вашего, звучит разумно, спасибо. Когда буду за машиной своей, попробую реализовать, благодарю!
Попробуйте ваш код изменить - делайте lst = {1}, и вы водите в каком порядке у вас вершины обрабатываются - будет точно такой же порядок почти на всех графах.
Я это предложил ещё 30 апреля (пункт 2):
https://habr.com/ru/articles/811051/comments/#comment_26779513
но понимания не получил :)
Да и Дейкстры и Форда-Беллмана в дефолтном варианте не обрабатывают такие графы. Самому эту фичу прикручивать нужно
С чего вы взяли? Обрабатывают, ещё как. Предварительная обработка не нужна.
Ну попробуйте сами тогда написать на С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? Точно нет повода задуматься?
Он имеет преимущество над скоростью выполнения Беллмана-Форда.
Но вы не сравнивали его с Беллманом-Фордом) Сравните его с ним, с простейшей оптимизацией "прекратить дальнейшую обработку, если за текущий проход ни один вес не изменился". Может быть очень интересно)
А что надо сделать, так это вывод о том, какой на самом деле алгоритм у вас получился, и чем он лучше существующих(и отличется ли от них вообще) ---> Как видим, мой алгоритм прошел все тесты и по времени не отличается от других известных. НО! Мой то еще с отрицательными весами умеет! Так что делаю, как вы говорите, вывод, что мой алгоритм рабочий.
Браво! Потрясающе! Великолепно! Но, к сожалению, ответ на исходный вопрос не был получен. Ознакомьтесь) https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm И никакой предобработки не нужно.
Подкину пару идей.
1) Метод наименьшего сопротивления (электрический). Проводится измерение суммы расстояний начального и конечного пути, и затем подбирается трассировка.
2) нейросетевой метод. Обучается нейросеть на куче примеров. Полученную функцию используем для аппроксимации кратчайшему пути. Можно использовать нейросеть Кохонена для кластеризации и картографирования 2д путей... Но метод может не подойти.
Любой из методов подразумевает перебор позиций. Тут уже сугубо машинная проблематика, упирающаяся в несколько-поточный процессор. Могу сказать что если перебор брать на нейросетевом методе на ядре cuda по скорости вычислений может превзойти классические методы благодаря кратному превосходству в многопоточности.
По методу 1 - вы предполагаете строить каждый граф в виде физической модели? Или как ещё можно измерить сумму расстояний предварительно не построив путь о.О
По методу 2 - как вы докажете что ваша обученная нейросеть обладает 100% точность решения задачи как любой математически доказанный алгоритм?
Ну и по комментарию про сугубо машинную проблематику - это не самом деле сверхмасштабная и дорогая ошибка. Если с таким подходом заходить в реальные проекты где алгоритмы важны, очень скоро выяснится что алгоритм с квадратичной сложностью от алгоритма с линейной может отличаться огромными переплатами за машиночасы. Легко может оказаться что вместо 1 nvidia tesla вам потребуется их 1000
А чем обычный алгоритм Дейкстры плох?
Находим самый маленький вес ребра и увеличиваем на него все веса. Путь при этом не изменится.
1) Алгоритм работает неправильно.
Пример:
graph = {
1: {2: 10},
2: {1: 10},
3: {2: 1}
}Результат: {2: 1, 1: 11}
Правильный результат: {1: 0, 2: 10, 3: infinity}
Чтобы избавиться от этой проблемы, нужно в строке, в которой вычисляется new_cost, заменить 0 на infinity и в строке, в которой инициализируется costs, сразу добавить туда стоимость пути до начального узла "costs = {1: 0}".
2) Алгоритм требует предварительной сортировки узлов по расстоянию от начального узла в "штуках рёбер" обходом в ширину. Алгоритм не выводит расстояния до недостижимых узлов.
Чтобы избавиться от этих проблем, нужно очередь узлов для обработки lst формировать не сразу, а по мере обработки.То есть, кроме множества processed (обработанные узлы) завести ещё множество unprocessed для узлов, которые ещё не добавлены в lst для обработки. Все узлы, которые после завершения алгоритма остались в unprocessed, являются недостижимыми.
3) Плохим случаям для Вашего алгоритма будет:
graph = {
1: {2: 6, 3: 5, 4: 3, 5: 0},
2: {1: 6, 3: 0, 4: 1, 5: 2},
3: {1: 5, 2: 0, 4: 0, 5: 1},
4: {1: 3, 2: 1, 3: 0, 5: 0},
5: {1: 0, 2: 2, 3: 1, 4: 0},
}Если добавить вывод обработанных узлов
print(f'Обработанные узлы: {lst}')то увидим, что узел 2 обрабатывался 4 раза.
Обработанные узлы: [1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 3, 2]Для экономии памяти желательно удалять из очереди обработанные узлы.
4) Алгоритм можно улучшить (для среднего случая), если очередь обрабатываемых узлов разбить на две:
обычная очередь - для узлов, которые переносятся из unprocessed
срочная очередь - для узлов, которые переносятся из processed
После всех этих манипуляций получаем алгоритм Левита. Сложность в худшем случае у него такая же, как у алгоритма Форда-Беллмана, но на реальных графах он почти не уступает алгоритму Дейкстры.
Алгоритм работает неправильно.
Если неправильно следовать алгоритму, то он и не будет правильно работать)) Специально для вас и для всех, кто так думает я включил подробнейшее пояснение, как правильно самостоятельно реализовать структуру графа. Ознакомьтесь еще раз, ваше высказывание не соответствует действительности.
Чтобы избавиться от этой проблемы, нужно ...
Ничего не нужно там делать, все там сделано. Отдельно написал про обработку недостижимых нод их вывод, все корректно работает.
Алгоритм требует предварительной сортировки узлов по расстоянию от начального узла в "штуках рёбер"
Никакой сортировки там не нужно, все работает без нее.
Плохим случаям для Вашего алгоритма будет:
С этим графом максимальное количество операций будет - 12. Плюс еще препроцессинг на 5 операций. Итого 17 операций против "наихудших" EV = 20*5=100 операций. Это ни разу не плохой случай ;)
Все что написано далее не требует никаких изменений в моем алгоритме. Вы его хотите переделать под алгоритм Левита, только зачем? Кстати спасибо за наводку, я не был знаком с этим алгоритмом. Я познакомился с ним, оформил реализацию и по предварительным тестам он работает намного медленнее. Плюс там, если не ошибаюсь, даже с реализацией 2-х очередей, в некоторых редких случаях сложность экспоненциальная. Я планирую сравнить Форда-Беллмана с оптимизацией, Левита и свой алгоритм на скорость выполнения стресс тестов. Следим за ситуацией, спасибо!
Специально для вас и для всех, кто так думает я включил подробнейшее пояснение, как правильно самостоятельно реализовать структуру графа.
Что Вы имеете ввиду? Не помню такого описания. Структуру графа в примере реализована точно так же, как в Ваших примерах - в виде словаря словарей.
Я пишу про код, который был указан в статье на момент написания комментария (вечером 30 апреля). Неправильный вывод Вашего кода я привёл.
Отдельно написал про обработку недостижимых нод их вывод, все корректно работает.
Я запустил Ваш код. Он вывел, цитирую: "Минимальные стоимости от источника до ноды". Все расстояния вывел неправильно, а Вы говорите корректно работает. Если позже Вы что-то исправили, то это не значит, что проблемы не было.
Никакой сортировки там не нужно, все работает без нее.
У Вас в статье написано "Важно! Нужно писать узлы графа в порядке их отдаленности от источника.". В комментариях Вы несколько раз указывали, что это можно сделать обходом в ширину. И даже добавили такой комментарий в текст статьи.
С этим графом максимальное количество операций будет - 12.
Неверно. 12 обработанных узлов во внешнем цикле. Для каждого обрабатываются 4 соседа. Итого 48 операций (предварительную обработку я не считаю).
против "наихудших" EV = 20*5=100 операций. Это ни разу не плохой случай
Вы неправильно понимаете, что такое сложность алгоритма. Тут важно не количество операций, а зависимость от размера входа. Например, для наивной сортировки сложность O(n^2), а максимальное количество операций (сравнений) n*(n-1)/2 в 2+ раза ниже, чем n^2.
Аналогично, в моём примере (1 + n*(n-1)/2) * (n - 1) релаксаций (попыток обновить расстояние). Это O(n^3) - худший случай. Ваш алгоритм обработал 12 узлов, но после исправлений, указанных мной в пункте 1, он будет обрабатывать на данном графе 11 узлов - в соответствии с приведённой формулой.
Вы его хотите переделать под алгоритм Левита, только зачем?
Его не нужно переделывать алгоритм Левита. Это и есть алгоритм Левита с небольшими техническими ошибками в реализации, на которые я указал в пунктах 1 и 2. Если Вы исправите (уже исправили?) эти ошибки по-другому, то получится алгоритм Левита с костылями, которые не пройдут коде-ревью в нормальной компании.
В изначальном Левите, кстати, тоже нет деления очереди обработки на обычную и срочную.
Плюс там, если не ошибаюсь, даже с реализацией 2-х очередей, в некоторых редких случаях сложность экспоненциальная.
Ошибаетесь. Экспоненциальная сложность получается при неправильной реализации. То есть, если добавлять не в конец, а в начало очереди.
Что Вы имеете ввиду? Не помню такого описания. Структуру графа в примере реализована точно так же, как в Ваших примерах - в виде словаря словарей
Структура да, а порядок сделан неверно. Я написал код создания моей структуры, вручную теперь не нужно этого делать. Пользуйтесь этим кодом и не ошибетесь. Вручную придется вводить только список ребер, впрочем в задачах часто на вход подаются графы такой структуры.
Все расстояния вывел неправильно, а Вы говорите корректно работает.
Странно, что у Вас неправильно выводится. Может быть у Вас граф какой-то необычный? Тот граф, который встроен в код в разделе обработки недостижимых нод работает корректно.
Вы несколько раз указывали, что это можно сделать обходом в ширину
Ну да, а что, это разве сортировка? Он за линейное время выполнится. Сортировка же за nlogn и то не всегда, в худшем случае n^2.
Неверно. 12 обработанных узлов во внешнем цикле
Да я вчера перед Вами извинился за ложную информацию, написал об этом. Я поздно заметил, что cycle_count стоял во внешнем цикле, я потом пересчитал все значения и вроде везде в коде исправил этот момент.
Вы неправильно понимаете, что такое сложность алгоритма
Да я понимаю, что такое сложность. Просто для наглядности считал количество операций. Если и там и там посчитать их, то можно что-то с чем-то наглядно сравнить, нежели просто формулу сложности смотреть. В той же быстрой сортировке сложность nlogn, но иногда n^2, когда массив "почти" отсортирован уже. Так как тогда сравнить, например, обычную сортировку с быстрой? По мне наглядно посчитать кол-во операций, сделанных там и там, пусть и не будет соответствовать формуле. Да, я считал по формуле кол-во операций, скоро я дополню статью сравнением скорости Spfa и Левита, а так же стандартного Беллмана-Форда. Там будет выглядить все нагляднее, ожидайте.
Это и есть алгоритм Левита
Это не он, у него реализация несколько другая. Плюс ко всему время его выполнения по предварительным тестам существенно выше, чем мой алгоритм. Чуть позже это продемонстрирую. Так же я заметил, что в моем алгоритме есть "лишние" операции, без которых можно обойтись, тем самым ускорив его слегка. Сегодня буду дополнять и обновлять содержимое статьи.
Структура да, а порядок сделан неверно.
Порядок правильный - в соответствии с Вашим описанием - сначала 1, затем ближайший (по обходу в ширину) сосед 2, затем недостижимый 3. Но неправильный ответ в моём примере выдаётся при любом порядке.
Странно, что у Вас неправильно выводится.
Я же привёл пример графа и пример вывода. Повторю вывод:
Результат: {2: 1, 1: 11}
Правильный результат: {1: 0, 2: 10, 3: infinity}
Ну да, а что, это разве сортировка?
Да, сортировка - в результате получаем список узлов, отсортированных по расстоянию (в штуках) от начального узла. Но если Вам не нравится слово "сортировка", то замените его на "предобработка". В любом случае, на сложность алгоритма она не влияет.
Сортировка же за nlogn и то не всегда, в худшем случае n^2.
Сортировку всегда можно сделать за nlogn. В некоторых случаях, используя информацию о сортируемых объектах, можно сортировать за O(n). Например, сортировка подсчётом.
Это не он, у него реализация несколько другая.
Тот код, который я видел 30 апреля после заголовка "UPD 2" - это именно Левит без оптимизации на 2 очереди (и без удаления из очереди). Привожу код (по памяти) с исправлением недочётов:
lst = [1] # Формируем очередность прохождения узлов графа
parents = {} # {Нода: его родитель}
costs = { 1: 0 } # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)
infinity = float('inf') # Бесконечность (когда минимальный вес до ноды еще неизвестен)
processed = set() # Множество обработанных нод
unprocessed = set([x for x in graph.keys() ])
unprocessed.remove(1)
for node in lst:
if node not in processed: # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
for child, cost in graph[node].items(): # Проходимся по всем детям
if child in unprocessed:
lst.append(child)
unprocessed.remove(child)
new_cost = cost + costs.get(node, infinity) # Путь до ребенка = путь родителя + вес до ребенка (если родителя нет, то путь до него = 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) # Когда все дети (ребра графа) обработаны, вносим ноду в множество обработанныхКак видно, изменения небольшие (но важные).
Тот код, который я увидел сегодня отличается только тем, что (как и Левите) используется очередь вместо списка. Это техническая деталь реализации, ещё более приближающая его к классической реализации Левита (по сути это реализация моего совета из пункта 3). Только, при использовании одной очереди, добавлять нужно в конец, а не в начало, чтобы не получить экспоненциальный рост в редких случаях.
если не ошибаюсь, даже с реализацией 2-х очередей, в некоторых редких случаях сложность экспоненциальная
Сейчас увидел, что Вы переделали код на очередь.
lst.appendleft(child) # Вновь добавляем эту ноду в список для того, чтобы обработать его зановоЭто как раз та реализация (добавление в начало), которая в некоторых редких случаях делает сложность экспоненциальной. А вторая (срочная) очередь используется, чтобы этого избежать.
По-моему, не получается тут экспоненциальной сложности. Да, каждая вершина может в очередь попасть O(n) раз. Вот и сложность суммарная O(VE).
По-моему, не получается тут экспоненциальной сложности.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Левита
При неправильной реализации алгоритма, используя вместо очередей M1′′ и M1′ дек и добавляя вершины из M0 в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.
Подробнее тут:
https://codeforces.com/blog/entry/3793
Ну да, но тут вроде вершины не добавляются в начало. Плюс вершина в очереди может быть только один раз. Я снчала тоже подумал про экспоненциальную сложность и пытался составить тест, но больше N раз я никакую вершину в очередь на обработку добавить не смог.
Ну да, но тут вроде вершины не добавляются в начало.
В реализации на e-maxx используется дек и вершины из processed (для повторной обработки) добавляются в начало. Так же сделано и у автора статьи в варианте с очередью (appendleft).
Я снчала тоже подумал про экспоненциальную сложность и пытался составить тест, но больше N раз я никакую вершину в очередь на обработку добавить не смог.
Я тоже сходу не смог придумать. Можно взять код по генерации графов из блога на codeforces и отловить (вывести на печать) граф, на котором обрабатывается миллион узлов.Затем, поняв принцип, сделать вручную небольшой граф.
P.S. Извиняюсь, неправильно посчитал количество операций. Самое большое количество - 60 операций, плюс более препроцессинг 20. Итого 80 против 100. Ну, наверное, можно назвать плохим случаем.
Злые вы, и я злой. Автор, почитай как хэш таблицы устроены, потом уже сложность оценивай. В целом для решения задачи рекомендую ознаклмиться со структурами данных.
Задача коммивояжёра , в чем разница?
Похоже, я придумал свой алгоритм поиска кратчайшего пути (upd: меня опередили...)