Задача

Имеется направленный граф G = (V, E), каждому ребру которого (i,j) Eприсвоен вес cij. Веса могут моделировать самые разные характеристики; в нашей интерпре- тации вес cij представляет стоимость прямого перехода от узла i к узлу j в графе.

Ранее мы уже обсуждали алгоритм Дейкстры для нахождения кратчайших путей в графах с положительной стоимостью ребер. Здесь рассматривается более сложная задача нахождения кратчайших путей, в которых стоимости могут быть отрицательными. Решение этой задачи актуально во многих ситуациях, среди кото- рых особенно важны две. Во-первых, отрицательные стоимости играют ключевую роль при моделировании некоторых процессов с кратчайшими путями: например, узлы могут представлять агентов в финансовых отношениях, а с.. — стоимость операции, в которой вы покупаете у агента i, а затем немедленно продаете агентуj. В этом случае путь представляет серию операций, а ребра с отрицательной сто- имостью — операции, приносящие прибыль. Во-вторых, алгоритм, который мы разработаем для обработки ребер с отрицательной стоимостью, во многих важных отношениях оказывается более гибким и децентрализованным, чем алгоритм Дейк- стры. Как следствие, он находит важное применение при проектировании алгорит- мов распределенной маршрутизации, определяющих наиболее эффективный путь в сети передачи данных.

В этом и двух следующих разделах рассматриваются две взаимосвязанные за- дачи:

♦ Для заданного графа G с весами (см. выше) решить, существует ли в G отрица- тельный цикл, то есть направленный цикл C, для которого


♦ Если граф не содержит отрицательных циклов, найти путь P от начального узла 5 к конечному узлу t с минимальной общей стоимостью; сумма


должна быть минимально возможной для любого пути s—t.

Обычно эта задача называется как задачей нахождения пути с минимальной стоимостью, так и за- дачей нахождения кратчайшего пути.

В приведенном выше финансовом примере отрицательный цикл соответствует прибыльной серии операций, которая возвращается к начальной точке: мы по- купаем у ip продаем i2, покупаем у i3 и т. д., в итоге возвращаясь к ii с чистой при- былью. Отрицательные циклы в таких сетях могут стать поводом для обращения в арбитраж.

Задачу нахождения пути s-t с минимальной стоимостью стоит рассматривать в предположении об отсутствии отрицательных циклов. Как показано на рис. 6.20, если бы в графе существовал отрицательный цикл C, путь Ps от 5 к циклу и другой путь P от цикла к t позволил бы построить путь s-t с произвольной отрицательной стоимостью: сначала по P5 переходим к отрицательному циклу C, «крутимся» в ци- кле сколько угодно раз и, наконец, используем Pt для перехода от C к конечному узлу t.

Рис. 6.20. В этом графе присутствуют пути s-t с произвольной отрицательной стоимостью (с многократным прохождением цикла C)


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача