Поиск цикла минимальной длины во взвешенном ориентированном графе
Дан ориентированный взвешенный граф. Требуется найти цикл, сумма весов которого должна быть минимальной, или доказать, что его не существует. Можно проходить через одну и ту же вершину по нескольку раз. Как это можно сделать наиболее оптимально? Может быть для такого случая есть какой-нибудь алгоритм?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
А кто у нас для ориентированных взвешенных графов имеется? Да Флойд-Уоршелл же.
Используя Флойда-Уоршелла, найдём кратчайшие пути между всеми парами вершин. Потом для каждой дуги A-B переберём остальные вершины С, смотря на сумму вес(A-B) + B->C + C->A