Главная » Java, Структуры данных и алгоритмы » Взвешенные графы

0

Как отмечалось в п. 12.3.2, стратегия поиска в ширину может использоваться для определения кратчайших маршрутов связного графа из одной точки до другой. Такой подход имеет определенный смысл в случаях, когда каждый путь не эквивалентен остальным путям. И наоборот, встречаются ситуации, в которых он просто не применим. Например, граф можно использовать для представления компьютерной сети (типа Интернета), и требуется отыскать наикратчайший путь для пересылки пакета с одной машины на другую. В таком случае поиск в ширину наверняка не приемлем, так как не все пути имеют одинаковую пропускную способность (то есть в одной сети может использоваться оптико-волоконная связь, а в другой — маломощная телефонная линия). Точно так же при использовании графа для представления дорог, связывающих города, мо- ж^т оказаться, что не все дороги одинаково пригодны для проезда: там могут быть и скоростные шоссе, и проселочные дороги. То есть речь идет об использовании таких графов, пути которых имеют различные свойства.

Взвешенным графом (weighted graph) называется граф, имеющий цифровое (например, целое число) обозначение w(e), соответствующее каждому пути е и называемое весом (weight) пути е. Пример взвешенного графа приводится на рис. 12.14.

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

По теме:

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