Ну возьмите, например, алгоритм Флойда, только измените min на max. А затем нетрудно восстановить за линейное время сам путь. Но если вам нужно это сделать на конкретно этом графе, то можно воспользоваться методом "пристального взгляда".
Пристальным взглядом не хотелось бы... Как говорил Чапаев в анекдоте: "Как бы это логически доказать?". А Флойдом я попробую, кажется я встречал то, о чем Вы говорите.
-- Вт мар 29, 2011 23:28:23 --Максим Маслов, спасибо, посмотрим.