<<
>>

Задача

Как вы уже знаете, графы часто используются для моделирования сетей, в которых происходит переход от одной точки к другой: например, дорог на транспортных развязках или каналов связи с промежуточными маршрутизаторами.
В результа- те задача поиска кратчайшего пути между узлами в графе вошла в число базовых алгоритмических задач. Даны узлы и и v; какой из путей u-v является кратчайшим? Также можно запросить более подробную информацию: задан начальный узел s, как выглядят кратчайшие пути от s ко всем остальным узлам?

Формальная постановка задачи кратчайших путей выглядит так: имеется на- правленный граф G = (V, E) с обозначенным начальным узлом s. Предполагается, что в графе существует путь от s к любому другому узлу G. Каждому ребру e назна- чена длина le > 0, которая обозначает время (или расстояние, или затраты), необхо- димое для перемещения по e. Для пути P длина P (обозначаемая l(P)) вычисляется как сумма длин всех ребер, входящих в P. Наша задача — определить кратчайший путь от s к каждому из других узлов графа. Следует упомянуть, что хотя задача сформулирована для направленного графа, случай ненаправленного графа обе- спечивается простой заменой каждого ненаправленного ребра e = (u, v) длины ie двумя направленными ребрами (u, v) и (v, u), каждое из которых имеет длину ie.

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

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

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