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

129
Рис. 4.7.
Выделенные ребра образуют минимальное связующее дерево,
которое соединяет все 15 MSA
4.5. ПОИСК КРАТЧАЙШИХ ПУТЕЙ 
ВО ВЗВЕШЕННОМ ГРАФЕ
Пока.сеть.Hyperloop.находится.в.процессе.создания,.маловероятно,.что.ее.раз-
работчики.настолько.амбициозны,.чтобы.хотеть.опутать.ею.сразу.всю.страну..
Вместо.этого.они,.скорее.всего,.захотят.минимизировать.затраты.на.прокладку.
трасс.между.ключевыми.городами..Стоимость.расширения.сети.до.отдельных.
городов,.очевидно,.будет.зависеть.от.того,.с.чего.строители.начнут.работы.
Определение.затрат.для.любого.заданного.начального.города.—.пример.задачи.
поиска.кратчайшего.пути.из.одного.источника..Эта.задача.гласит:.«Каков.крат-
чайший.путь.с.точки.зрения.общего.веса.ребра.от.некоторой.вершины.к.любой.
другой.вершине.во.взвешенном.графе?»
4.5.1. Алгоритм Дейкстры
Алгоритм.Дейкстры.решает.задачу.поиска.кратчайшего.пути.из.одной.вершины..
Задается.начальная.вершина,.и.алгоритм.возвращает.путь.с.наименьшим.весом.
к.любой.другой.вершине.во.взвешенном.графе..Он.также.возвращает.минималь-
ный.общий.вес.для.пути.из.начальной.вершины.к.каждой.из.оставшихся..Алгоритм.
Дейкстры.начинается.из.одной.исходной.вершины,.а.затем.постоянно.исследует.

---

130
Глава 4.
Графовые задачи
ближайшие.к.ней.вершины..По.этой.причине.алгоритм.Дейкстры,.как.и.алгоритм.
Ярника,.является.жадным..Когда.алгоритм.Дейкстры.исследует.новую.вершину,.
он.проверяет,.как.далеко.она.находится.от.начальной.вершины,.и.обновляет.это.
значение,.если.находит.более.короткий.путь..Подобно.алгоритму.поиска.в.ширину,.
он.отслеживает,.какие.ребра.ведут.к.каждой.вершине.
Алгоритм.Дейкстры.выполняет.следующие.шаги.
1.. Добавить.начальную.вершину.в.очередь.с.приоритетом.
2.. Извлечь.из.очереди.с.приоритетом.ближайшую.вершину.(вначале.это.только.
исходная.вершина).—.назовем.ее.текущей.
3.. Исследовать.все.соседние.вершины,.связанные.с.текущей..Если.они.ранее.не.
были.записаны.или.если.ребро.предлагает.новый.кратчайший.путь,.то.для.
каждой.из.этих.вершин.записать.расстояние.до.начальной.вершины,.указать.
ребро,.соответствующее.этому.расстоянию,.и.добавить.новую.вершину.в.оче-
редь.с.приоритетом.
4.. Повторять.шаги.2.и.3.до.тех.пор,.пока.очередь.с.приоритетом.не.опустеет.
5.. Вернуть.кратчайшее.расстояние.до.каждой.вершины.от.начальной.и.путь,.
позволяющий.добраться.до.каждой.из.них.
Код.алгоритма.Дейкстры.включает.в.себя.
DijkstraNode
.—.простую.структуру.
данных.для.отслеживания.затрат,.связанных.с.каждой.исследованной.вершиной,.
и.сравнения.вершин..Это.похоже.на.класс.
Node
,.описанный.в.главе.2..Он.также.
включает.в.себя.вспомогательные.функции.для.преобразования.возвращенного.
массива.расстояний.во.что-то.более.простое,.удобное.для.поиска.по.вершине.
и.вычисления.кратчайшего.пути.до.конкретной.конечной.вершины.из.словаря.
путей,.возвращаемого.
dijkstra()
.
Чем.долго.рассуждать,.лучше.сразу.приведем.код.алгоритма.Дейкстры.(лис-
тинг.4.13)..Разберем.его.построчно..Весь.код.находится.в.файле.
WeightedGraph.java
.