sashx, 1) идете от s до цикла.
2) крутитесь там проивзольное количество раз.
3) идете до t.
Получаете сколь угодно длинный путь.
Даже если запретить ходить по уже обойденным вершинам, то все-равно остается только полный перебор.
В очень частном случае, когда вершин мало можно построить искуственный граф, где вершинами будут подмножества вершин исходного графа X какая вершина последняя. Этот граф уже будет ациклический и можно по нему однозначно восстановить путь в исходном графе. Но это работает максимум для ~20 вершин максимум.
Максимальный путь в графе с циклами найти тяжело. Обходом в ширину - вообще никак. Только полным перебором (что является скорее рекурсивным обходом в глубину, но с откатами).
Если граф дерево или ориентированный ациклический, то работает любой обход.
Простой
Средний
