Алгоритмы Беллмана-Форда и Флойда-Уоршелла. Транзитивное замыкание графа
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- Занятие факультатива ОНУ им Мечникова
вначале немного напомнил про основные концепции поиска кратчайших путей в нагруженных графах.
Основная часть занятия посвящена алгоритмам поиска, которые работают даже для графа с дугами отрицательного веса - в отличии от алгоритма Дейкстры - а именно мы рассматриваем алгоритм Беллмана-Форда и алгоритм Флойда-Уоршелла, а также применение аналога алгоритма Флойда-Уоршелла для нахождения транзитивного замыкания графа.
В первой части я использую слайды А.А.Кубенского, а во второй статью
neerc.ifmo.ru/w...
(в Украине данный ресурс открывается через VPN).
Задачи вот здесь:
www.eolymp.com...
Рассмотрены и решены задачи
www.eolymp.com... Форд-Беллман
и
www.eolymp.com... Флойд - 1