Замечательное видео где все расставлено по своим местам и имеется вариативность решений. Но было бы здорово видеть какие нибудь файлы с кодом в описании видео, и абстрагировать код о какого либо проекта (ввод данных из текстового файла) для лучшей наглядности. Успехов, че =)
Спасибо за видео! Можно ли с помощью Дейкстры найти все кратчайшие пути? То есть у нас могут быть более чем один "path"? Или надо использовать другой алгоритм?
@@op_ulstu Я неправильно наверно выразилась - алгоритм Floyd ищет все кратчайшие пути попарно, но у меня всё-таки задачи более похоже на алгоритмДейкстры. То есть мне нужно найти все возможные пути от Start до Finish, где Start и Finish фиксированной… В отличие от видео нужно распечатать все пути от Start до Finish если их несколько. Надо структуру from дополнить? Или другой алгоритм искать?
@@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 различных кратчайших пути.
Огромное СПАСИБО! Объяснение ГРОССМЕЙСТЕРА...Каждое выражение подчеркивает мастерство и знание предмета.
Это лучшее объеснение алгоритма которое я нашел в просторах интернета. Спасибо за видос
Ваш канал имба, столько всего полезного собрали) алгоритмы чётко и ясно объясняются. Жаль, что курсу не суждено выйти, получилось бы здорово, думаю
Очень грамотно и лаконично! Бесконечный респект таким преподавателям)
добрый день. спасибо большое за алгоритм!
Замечательное видео где все расставлено по своим местам и имеется вариативность решений. Но было бы здорово видеть какие нибудь файлы с кодом в описании видео, и абстрагировать код о какого либо проекта (ввод данных из текстового файла) для лучшей наглядности. Успехов, че =)
Спасибо большое
Спасибо за видео!
Можно ли с помощью Дейкстры найти все кратчайшие пути? То есть у нас могут быть более чем один "path"? Или надо использовать другой алгоритм?
Ответ на ваш вопрос - чуть далее по плейлисту, в видеозаписях про алгоритм Флойда-Уоршелла.
@@op_ulstu Я неправильно наверно выразилась - алгоритм Floyd ищет все кратчайшие пути попарно, но у меня всё-таки задачи более похоже на алгоритмДейкстры. То есть мне нужно найти все возможные пути от Start до Finish, где Start и Finish фиксированной… В отличие от видео нужно распечатать все пути от Start до Finish если их несколько. Надо структуру from дополнить? Или другой алгоритм искать?
@@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 различных кратчайших пути.
for (auto& [to, weiht] : graph[nerest]) { вот эта строчка отказывается работать
Проверьте, что в вашем компиляторе включена поддержка стандарта C++17.
@@op_ulstuскажите, будут ли выходить новые видео или у вас появились какие-то другие проекты?
@@op_ulstu такая же проблема