Так пожалуйста, решайте головой! Берите карту местности вместо смартфона c навигатором и на листочке считайте, как быстрее всего доехать из условной Москвы до Сочи. Уверен, занятие Вам будет по душе :)
А каким образом Вы представляете граф во входную точку программы? Произвольные ноды и описание их соседей? Насколько помню, даже та же матрица смежностей реализует представление графа "по порядку". Даже возьмем ту же карту и текущую геопозицию. На вход программе уже будет произведен поиск в ширину и все будет по порядку. Не представляю, как можно подать на вход описание нод в разнобой, м.б. имеет место быть где-то, но это можно обработать в коде, поэтому, возможно Вы и правы насчет сложности.
Я об этом написал вообще-то, что сложность с реализацией приоритетной очереди будет такая, но она не всегда будет такой, в редких случаях "быстрее будет медленный алгоритм", как бы тавтологически не звучало.
Аргументируйте, пожалуйста. Приведите пример графа и разберемся вместе. По существу, это пальцем в небо тыкнули.
Спасибо, что привели пример такого вида графа. Я протестировал этот граф, саму цепочку нод он правильно посчитал, но вот с расстоянием да, ошибся. Как вариант, модифицировал код, чтобы он просто проходил по цепочке и обновлял расстояние. Посмотрите еще раз на функцию "get_shortest_path". Костыль, но работает :)
"мне понравилось изучать алгоритмы, я много интересовался задачей о кратчайших путях и думаю, что мне удалось придумать что-то новое, но в моём окружении нет достаточно компетентных людей, которые бы молги объяснить получилось или нет и почему. Поэтому я напишу статью на хабре и может там мне подскажут"
Вы абсолютно правы, я самоучка, у меня нет в окружении ни преподавателей, ни знакомых, кто этим интересуется.
Рвение похвально, но хабр не место для таких статей
А теперь приведу текст политики самого хабра
Считаю, что ставить минус и "хейтить" за то, чем пользуешься по правилам и следуя философии площадки наравне с "моргать дальним и сигналить впереди едущему автомобилю, который едет по ПДД", мол я тут уже не первый год "за рулем", знаю как тут все устроено... В общем, суть уловили, я думаю.
нобелевскую премию не дадут
Здесь, очевидно, была шутка, но если и Вы шутили, то ок
Спасибо большое, как начинающему автору, очень приятно!
Так пожалуйста, решайте головой! Берите карту местности вместо смартфона c навигатором и на листочке считайте, как быстрее всего доехать из условной Москвы до Сочи. Уверен, занятие Вам будет по душе :)
Спасибо за добрую оценку!
А каким образом Вы представляете граф во входную точку программы? Произвольные ноды и описание их соседей? Насколько помню, даже та же матрица смежностей реализует представление графа "по порядку". Даже возьмем ту же карту и текущую геопозицию. На вход программе уже будет произведен поиск в ширину и все будет по порядку. Не представляю, как можно подать на вход описание нод в разнобой, м.б. имеет место быть где-то, но это можно обработать в коде, поэтому, возможно Вы и правы насчет сложности.
Я об этом написал вообще-то, что сложность с реализацией приоритетной очереди будет такая, но она не всегда будет такой, в редких случаях "быстрее будет медленный алгоритм", как бы тавтологически не звучало.
Аргументируйте, пожалуйста. Приведите пример графа и разберемся вместе. По существу, это пальцем в небо тыкнули.
Спасибо за упрощение объяснения! Надеюсь, кому-то оно позволит понять мысль лучше.
Исправил код, посмотрите, пожалуйста, еще раз на реализацию
Спасибо, что привели пример такого вида графа. Я протестировал этот граф, саму цепочку нод он правильно посчитал, но вот с расстоянием да, ошибся. Как вариант, модифицировал код, чтобы он просто проходил по цепочке и обновлял расстояние. Посмотрите еще раз на функцию "get_shortest_path". Костыль, но работает :)
Вы абсолютно правы, я самоучка, у меня нет в окружении ни преподавателей, ни знакомых, кто этим интересуется.
А теперь приведу текст политики самого хабра
Считаю, что ставить минус и "хейтить" за то, чем пользуешься по правилам и следуя философии площадки наравне с "моргать дальним и сигналить впереди едущему автомобилю, который едет по ПДД", мол я тут уже не первый год "за рулем", знаю как тут все устроено... В общем, суть уловили, я думаю.
Здесь, очевидно, была шутка, но если и Вы шутили, то ок
Не совсем понял, что не так с этим примером? Вы откуда и куда хотите попасть? Если с 1 до 4 ноды, то будет 10, т.е. все правильно.
Вот тут очень спорно, на самом деле, но я не силен в оценивании ассимптотики, поэтому, думаю, коллеги смогут что-то сказать по этому поводу.
Спасибо за фидбэк!