Главная » Java, Структуры данных и алгоритмы » Кратчайшие маршруты

0

Допустим, G — взвешенный граф. Длина (вес) маршрута — это сумма длин (весов) каждого пути в Р. То есть если Р— (vo,vj), (v\,v2), (vfc-hvk)> то длина Р, обозначаемая как w(P), определяется как

Рис. 12.14. Взвешенный граф, узлы которого представляют крупнейшие аэропорты США, а пути — расстояния в милях. Данный граф имеет маршрут из JFK до LAX общим весом в 2777 (через ORD и DFW), и это минимальный вес маршрута от JFK до LAX во всем графе

города, а вес путей в G обозначает стоимость поездки из одного города до другого. Если некто пожелает оплатить поездку скажем, из JFK до ORD, то стоимость пути окажется отрицательной. Если же оплачивать поездку из ORD до JFK, то образуется цикл с отрицательным весом, и расстояние невозможно определит*». Это означает, что можно выстроить в G маршрут (с циклами) из любого города А до города Б, который вначале ведет в JFK, а затем кру!ится по замкнутому кругу из JFK в ORD и обратно, прежде чем попасть в Б. Наличие такого маршрута позволяет составить произвольные маршруты с низкой отрицательной стоимостью (и в этом случае заработать целое состояние на этом процессе). Но расстояние не может выражаться произвольными отрицательными числами. Следовательно, всякий раз, когда используется вес путей для представления расстояний, следует избегать использования циклов с отрицательным весом.

Предположим, имеется взвешенный граф G и требуется найти кратчайший маршрут из одного узла v до другого узла, рассматривая расстояние как вес путей. Для этого можно применить несколько алгоритмов. Первый алгоритм используется в простых, но распространенных случаях, когда веса всех путей в Сне отрицательные (то есть w(e) > 0 для каждого пути ев G). Следовательно, наперед известно, что здесь циклы с отрицательным весом отсутствуют. Напомним, что в особых случаях вычисления кратчайшего пути, когда вес каждого пути равен 1, проблема решается с помощью BFS-алгоритма, показанного в п. 12.3.2.

Существует интересный подход к решению проблемы централизованного распределения данных, основанный на проектной модели каскадного метода (п. 11.4.2). В этой модели использован принцип выбора наилучшего из имеющихся вариантов в каждой из итераций. Эта парадигма

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии