Почему-то по моим рассуждениям получается, что это алгоритм поиска в глубину,
но тогда мы должны сперва находить неоптимальные решения (перевести одного человека на ту сторону, привезти его обратно, потом другого, и т.д.)
Не могли бы вы пояснить этот момент?

UPD: ааа, или мы так и находим их, просто выводим самый быстрый среди них! Я прав?
UPD2: только высчитывать самый медленный мы так и не пойдем из-за ленивости, наверное.