Алгоритм Дейкстры: два варианта реализации

[@avoidperil6171]

Это лучшее объеснение алгоритма которое я нашел в просторах интернета. Спасибо за видос

[@dirrry2331]

Ваш канал имба, столько всего полезного собрали) алгоритмы чётко и ясно объясняются. Жаль, что курсу не суждено выйти, получилось бы здорово, думаю

[@muznadzor554]

Очень грамотно и лаконично! Бесконечный респект таким преподавателям)

[@dfddtx1523]

Замечательное видео где все расставлено по своим местам и имеется вариативность решений. Но было бы здорово видеть какие нибудь файлы с кодом в описании видео, и абстрагировать код о какого либо проекта (ввод данных из текстового файла) для лучшей наглядности. Успехов, че =)

[@vidruska]

Спасибо за видео! Можно ли с помощью Дейкстры найти все кратчайшие пути? То есть у нас могут быть более чем один "path"? Или надо использовать другой алгоритм?

[@op_ulstu]

Ответ на ваш вопрос - чуть далее по плейлисту, в видеозаписях про алгоритм Флойда-Уоршелла.

[@vidruska]

@@op_ulstu Я неправильно наверно выразилась - алгоритм Floyd ищет все кратчайшие пути попарно, но у меня всё-таки задачи более похоже на алгоритмДейкстры. То есть мне нужно найти все возможные пути от Start до Finish, где Start и Finish фиксированной… В отличие от видео нужно распечатать все пути от Start до Finish если их несколько. Надо структуру from дополнить? Или другой алгоритм искать?

[@op_ulstu]

@@vidruska Вы можете попробовать сделать вектор from двумерным, чтобы в ячейке с индексом to сохранять не одного, а сразу всех возможных предков вершины to на каком-то кратчайшем пути (добавится условие else if (dist[to] == dist[nearest] + weight) from[to].push_back(nearest); ). Затем вам придётся написать рекурсивную функцию, перебирающую все возможные пути от finish до start по этому массиву. Правда, имейте в виду, что количество кратчайших путей между start и finish в графе может быть экспоненциальным, и в общем случае вывести их все не получится. Рассмотрите, например, граф: 7 12 1 2 100 1 2 100 2 3 100 2 3 100 3 4 100 3 4 100 4 5 100 4 5 100 5 6 100 5 6 100 6 7 100 6 7 100 Даже в этом маленьком графе между вершинами 1 и 7 есть 64 различных кратчайших пути.

[@АлексейНяшин-к6б]

Спасибо большое

[@chto_to_ne_tak.]

for (auto& [to, weiht] : graph[nerest]) { вот эта строчка отказывается работать

[@op_ulstu]

Проверьте, что в вашем компиляторе включена поддержка стандарта C++17.

[@tusman4ik]

​@@op_ulstuскажите, будут ли выходить новые видео или у вас появились какие-то другие проекты?

[@craptowel3516]

@@op_ulstu такая же проблема