2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нахождение критического пути для ориентированного графа
Сообщение29.03.2011, 21:35 
Задание:
Для ориентированного графа с заданной для ребер длиной найти критический путь.
дуга Длительность
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
Перерыл все источники. Ни в одном из них не нашел примеров нахождения КРИТИЧЕСКОГО пути, есть только кратчайший. Помогите, пожалуйста, с литературой, если приходилось встречать где-нибудь подробное решение. Или, если не затруднит, объясните так.

 
 
 
 Re: Нахождение критического пути для ориентированного графа
Сообщение29.03.2011, 21:57 
Ну возьмите, например, алгоритм Флойда, только измените min на max. А затем нетрудно восстановить за линейное время сам путь. Но если вам нужно это сделать на конкретно этом графе, то можно воспользоваться методом "пристального взгляда".

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

 
 
 
 Re: Нахождение критического пути для ориентированного графа
Сообщение29.03.2011, 22:27 
cyb12 в сообщении #428912 писал(а):
Ну возьмите, например, алгоритм Флойда, только измените min на max. А затем нетрудно восстановить за линейное время сам путь. Но если вам нужно это сделать на конкретно этом графе, то можно воспользоваться методом "пристального взгляда".

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

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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group