Поиск кратчайшей дороги - NP-полная задача. Решить оптимально за приемлимое время её невозможно. Яндекс себя переоценил. Ну а просто короткой дорогой можно считать любую, которая короче некоторой другой. С такой точки зрения всё нормально на картинке ).
> Поиск кратчайшей дороги - NP-полная задача. Решить оптимально за приемлимое время её невозможно. Яндекс себя переоценил. Ну а просто короткой дорогой можно считать любую, которая короче некоторой другой. С такой точки зрения всё нормально на картинке ).
Это кратчайший гамильтонов путь - NP-полная задача. Кратчайший путь отлично решается за О((E+V) log V) где E количество рёбер, V вершин в графе, а это полиномиальная оценка. Так что на картинке фэйл )
Сейчас, сейчас