Нахождение критического пути для ориентированного графа

[sealab2021]

Задание:
Для ориентированного графа с заданной для ребер длиной найти критический путь.
дуга Длительность
1-2 2
1-3 4
2-3 3
2-5 6
3-4 2
3-5 1
4-5 3
4-8 2
5-6 4
5-8 5
6-7 3
7-8 6
Перерыл все источники. Ни в одном из них не нашел примеров нахождения КРИТИЧЕСКОГО пути, есть только кратчайший. Помогите, пожалуйста, с литературой, если приходилось встречать где-нибудь подробное решение. Или, если не затруднит, объясните так.

[cyb12]

Ну возьмите, например, алгоритм Флойда, только измените min на max. А затем нетрудно восстановить за линейное время сам путь. Но если вам нужно это сделать на конкретно этом графе, то можно воспользоваться методом "пристального взгляда".

[Maslov]

Посмотрите здесь:
Майника Э. Алгоритмы оптимизации на сетях и графах
Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика. Графы, матроиды, алгоритмы

[sealab2021]

cyb12 в сообщении #428912 писал(а):

Ну возьмите, например, алгоритм Флойда, только измените min на max. А затем нетрудно восстановить за линейное время сам путь. Но если вам нужно это сделать на конкретно этом графе, то можно воспользоваться методом "пристального взгляда".

Пристальным взглядом не хотелось бы... Как говорил Чапаев в анекдоте: "Как бы это логически доказать?". А Флойдом я попробую, кажется я встречал то, о чем Вы говорите.

-- Вт мар 29, 2011 23:28:23 --

Максим Маслов, спасибо, посмотрим.