Алгоритм Флойда
Вставка
- Опубліковано 5 лют 2025
- Алгоритм поиска кратчайших путей Флойда позволяет весьма простым способом создать матрицу выражающую все существующие в графе кратчайшие пути. До просмотра этого урока, пожалуйста, убедитесь, что вы знаете как выражать граф с помощью матрицы (если вы этого ещё не знаете, не беда, посмотрите видео урок как раз на эту тему • Представление графа в ... ).
спасибо, Иисус
Ииусус любит тебя
Спасибо за видео. Интересно слушать про всякие алгоритмы. По чаще бы
Благодарю за положительный отзыв. Поверьте мне, если-бы в дне было по 100 часов, то было-б всего на много больше. Я банально не успеваю иногда сделать всё что планирую.
Алгоритмы - это особенно сложная вещь, так как я их не могу просто с ходу объяснить, надо сначала продумать как это сделать, а на это уходит время. Вот даже это видео записывалось дважды, и то наверное в некоторых местах было совсем не элементарно понимать, что происходит и почему.
Вы очень хорошо и не нудно объясняете, спасибо большое!
Шикарное обьяснение. Автору спасибо.
Спасибо вам большое. Очень помогли понять алгоритм. Всё доступно и красиво объясняете.
Спасибо, Володя, очень добротный материал. Правда, всё исчерпывающе-понятно.
Спасибо за видео! Только после вашего объяснения смог разобраться с этим алгоритмом.
Я перечитала немерено лекций и примеров по этому, но все время какие то моменты оставались не до конца ясны, а тут все идеально, просто как говорят "прожевали и в рот положили". Спасибо за урок))
Красавчик, интересно узнавать что то так наглядно
Спасибо за видео! Некоторые моменты не понимала, теперь всё понятно.
Очень хорошо и понятно изложено. Спасибо!
Спасибо вам за ваш труд.
Спасибо большое Вам!)
Большое спасибо, реально помогло представить как работает алгоритм.
Пы.Сы. за маршрут из узла в узел отдельное спасибо, очень долго не мог придумать как его сделать.
UPD: Только что закодил это в с++ и столкнулся с недочетом. Необходимо также проверять существование пути из "В" в "С"(может я прослушал этот момент в видео, но в псевдокоде я этого не вижу)
Меня это сразу смутило при просмотре видео, что нет такой проверки. Видимо, оправдано.
Владимир, спасибо за интересный урок!
Так подробно о Флойде даже на лекции не рассказали. =)
И реализация с 2мя таблицами очень хороша. Взял себе в копилку мудростей. =)
Но есть одно пожелание: доску бы побольше, а то информация не влезает, приходится стирать, и при дальнейшем объяснении приходится удерживать в голове нарисованное ранее в дополнении к пониманию объясняемого сейчас.
Да и так более наглядней будет.
Например, в данном конкретном уроке можно было бы нарисовать граф, рядышком составить таблицы смежности и истории, реализацию алгоритма, и тут же прогнать его по данному графу с иллюстрацией изменения таблиц. =)
+Анри Байер На бо́льшую доску не хватает места: ua-cam.com/video/VfpvKrtD7zo/v-deo.html
Отличное видео. Просто и доходчиво.
Но на мой взгляд стоило бы чуть-чуть расшить область представления - использовать вторую доску (или использовать одну, но большего размера) чтобы иметь на виду дополнительную информацию, в данном случае было бы неплохо видеть граф(и на нем было бы удобнее показывать связи) и матрицы.
Начинать смотреть с 1:20
Крутое видео, но хотелось бы увидеть конкретный пример того, как этот алгоритм решается на бумаге, для большего понимания.
Спасибо большое!
Спасибо большое! Очень хорошо объясняете!
Благодарю за пояснение, теперь вроде как все стало понятно. Я могу ошибаться, но в некоторых случаях одного прохода алгоритма оказывается недостаточно, чтобы пройтись по всем элементам.
Красава! Спасибо тебе большое. Круто объясняешь!!!!
Очень интересно, спасибо.
Огромное спасибо! Отлично прям и всё понятно! Владимир, а как можно с Вами связаться у меня есть интересная задача про конкретную практическую задачу с электрическими машинами.
Хорошо объяснили!
Но одно замечание:
Всё-таки в истории нужно было хранить b, так как эта вершина будет предыдущей, а не предыдущая от неё, так как иначе будет 0, так как самая первая будет совпадать с последней.
Автору конечно спасибо, но может я ещё не совсем понял смысл данного алгоритма к графам... но такое впечатление, что если перед нами есть граф, мы видим как он связан, видим вес связей, то цель в том чтобы рассказать компьютеру какой путь короче, чтобы он нам сказал какой путь короче ^_^
P.S. и как то хотелось бы видеть конкретный нарисованный граф, на котором этот алгоритм объясняется...
Володя, на 13:25 Вы пишете H[A,C]= H[A,B] . Но это ведь матрица истории, там не указывается вес, поэтому корректнее H[A,C]= B
И по этой же матрице на 19:01 , чтобы узнать путь от вершины 1 до любой другой следует смотреть числа по горизонтали, а не по вертикали, насколько я понял
В матрице Н нет веса. Н[A,C] предидющий шаг, а не вес.
Если кто-нить попробует реализовать этот алгоритм на практике, то вполне вероятно наткнуться на простую ошибку...
В псевкокоде в записи (три нижние строки)
If W[A,C] > W[A,B]+W[B,C]
W[A,C] = W[A,B]+W[B,C]
H[A,C] = H[A,B]
может быть не совсем понятно назначение последней строки.
Ведь если использовать оператор IF без begin-end, или всё тех же фигурных скобок { ... } то на практике (при такой записи) в нашей программе вторая строка выполниться только при истинном условии, а третья будет срабатывать каждый раз (не зависимо от условия).
Как вариант отформатировать код с использованием соответствующих операторов начала-конца блока, например так:
If W[A,C] > W[A,B]+W[B,C]
{
W[A,C] = W[A,B]+W[B,C]
H[A,C] = H[A,B]
}
Правильнее даже так:
If ( W[A,C] > W[A,B]+W[B,C] )
{
W[A,C] = W[A,B]+W[B,C]
H[A,C] = H[A,B]
}
Но это только моё мнение, и на него можете не обращать внимания :-)
В псевдокоде блоке обозначаются отступами.
Если в языке, на котором вы это реализуете, это не так - естественно, что нужно выделить этот блок.
Я с псевдокодом не работал, но пару недель назад смотрел код на Питоне - там так же блоки отступами отделяют. Интерестно смотрится.
я не понял один нюанс, в конечном примере я могу пойти с 1-3 вес будет 15, но вы предлагаете, как оптимальный вариант, пойти с 1-5-4-3, тогда вес будет 5+11+8=24
Спасибо
Спасибо!
спасибо)
Спасибо за видео, очень помогло! А можно ли как-то узнать все возможные пути из одной точки в другую, к примеру:
А - В, 3
А - С, 2
С - В, 1
Как я могу вывести 2 маршрута, не только один? А => B, A => C => B?
#ucode?)
@@МаксимМарьенко-я7з +
@@ddw2022 я думаю, нужен алгоритм Деикстры, Флоида только для ориентированных
@@МаксимМарьенко-я7з не только
А как насчет того что в графе может быть несколько таких коротких путей? Скажем так из одной вершины в другую может быть два одинаковых по сути пути.
Спасибо тебе, Иисус!
Выступил с семинаром по данной теме, получил 5. Спасибо вам огромное!
Никто не сказал главного: в алгоритме ошибка!
Цикл for each as C нужно поставить на первое место и убать странное if w[a,b]!=inf. Откуда оно там?
Но все равно спасибо за идею с матрицей истории
+Валя Журавская я сейчас сходу не обосную, почему (нужно опять вникать в него), но проблема в том, что реализованный по данной инструкции алгоритм не работает.
+Валя Журавская Я согласна с Игорем Балицким в том, что вершину С нужно перебирать во внешнем цикле. Если мы рассматриваем вершины А и В с пересадкой в вершине С, то равенство должно выглядеть так АВ>AC+CB. А у нас получается АС>АВ+ВС
Скажите пожалуйста, а у вас уроки про алгоритм Данцига, А то информации о нём мало и сложно разобраться
Максим Антосюк Этого нет, и в ближайшее время наверно не будет. Времени не хватает снимать серьёзные видео.
spasibo za video
работает ли данный алгоритм для неориентированного графа?
+Павел Теплостанский Да, конечно. У вас путь назад никогда не пойдёт, так как значение туда+обратно всегда получится больше первоначального.
Правда стоит отметить, что в этом случае Флойд - далеко не самый оптимальный алгоритм.
Всегда знал что Иисус программист от Бога.
алгоритм, предложенный автором, не рабочий. в нем есть ошибки
почему вас нет в моём универе??? =(
Можно на java код ?
в js бесконечность Infinity
Классное видео, все понятно. Единственный минус - волосы... Их много... Не очень приятно смотреть...
подстрегитесь если мешают)
ААА сложнааа
Нифига не понятно
Ставь лайк, если экземпляр человеческого класа
esli mojno delayte tak chtob s doski bilo vidno xorosho
Вы имеете ввиде, что отблеск мешает или то, что иногда я перед доской стою? Я знаю, что сейчас у меня не совсем нормальное освещение, но постораюсь следить чуть больше за углом падения света.
Da ya govoryu pro osveshenie
афтар хиппи
Спасибо!