Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

4.3. ПОИСК КРАТЧАЙШЕГО ПУТИ
Hyperloop.—.настолько.быстрый.транспорт,.что.для.оптимизации.времени.в.пути.
между.станциями,.вероятно,.расстояние.между.ними.имеет.гораздо.меньшее.зна-
чение,.чем.то,.сколько.прыжков.потребуется.(сколько.станций.придется.посетить),.
чтобы.добраться.от.одной.станции.до.другой..Каждая.станция.может.означать.за-
держку,.поэтому,.как.и.при.полетах.на.самолете,.чем.меньше.остановок,.тем.лучше.
В.теории.графов.множество.ребер,.соединяющих.две.вершины,.называется.
пу-
тем
..Другими.словами,.путь.—.это.способ.перехода.от.одной.вершины.к.другой..
В.контексте.сети.Hyperloop.набор.труб.(ребер).представляет.собой.путь.из.од-
ного.города.(вершины).в.другой.(другая.вершина)..Поиск.оптимальных.путей.
между.вершинами.—.одна.из.наиболее.распространенных.задач,.для.которых.
используются.графы.
Неформально.мы.также.можем.представить.как.путь.список.вершин,.последова-
тельно.соединенных.друг.с.другом.ребрами..Такое.описание.—.это,.в.сущности,.
другая.сторона.той.же.монеты..Это.все.равно.что.взять.список.ребер,.выяснить,.
какие.вершины.они.соединяют,.сохранить.список.вершин.и.отбросить.ребра..
В.следующем.кратком.примере.мы.найдем.список.вершин,.соединяющий.два.
города.в.сети.Hyperloop.
4.3.1. Пересмотр алгоритма поиска в ширину
В.невзвешенном.графе.поиск.кратчайшего.пути.означает.поиск.пути.с.наимень-
шим.количеством.ребер.между.начальной.и.конечной.вершинами..При.построении.
сети.Hyperloop,.возможно,.имеет.смысл.сначала.подключить.самые.отдаленные.
города.на.густонаселенных.побережьях..Возникает.вопрос:.какой.путь.между.
Бостоном.и.Майами.кратчайший?
СОВЕТ
В.этом.разделе.предполагается,.что.вы.прочитали.главу.2..Прежде.чем.продолжить,.
убедитесь,.что.знакомы.с.алгоритмом.поиска.в.ширину.(BFS),.описанным.в.ней.

---