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

if 
(pathMap.size() == 0) {
return 
List.
of
();
}
LinkedList path = 
new 
LinkedList<>();
WeightedEdge edge = pathMap.get(end);
path.add(edge);
while 
(edge.u != start) {
edge = pathMap.get(edge.u);
path.add(edge);
}
Collections.
reverse
(path);
return 
path;
}
В.первых.строках.
dijkstra()
.используются.структуры.данных,.с.которыми.вы.
уже.знакомы,.за.исключением.
distances
.—.заполнителя.для.расстояний.до.каж-
дой.вершины.графа.от.
root
..Первоначально.все.эти.расстояния.равны.
0
,.так.как.
мы.еще.не.знаем.значения.каждого.из.них,.—.именно.для.их.определения.и.при-
меняем.алгоритм.Дейкстры!
public 
DijkstraResult dijkstra(V root) {
int 
first = indexOf(root); // найти начальную вершину 
// поначалу расстояния неизвестны
double
[] distances = 
new double
[getVertexCount()];
distances[first] = 0; // корневая вершина равна 0
boolean
[] visited = 
new boolean
[getVertexCount()];
visited[first] = 
true
;
// как добраться до каждой вершины
HashMap pathMap = 
new 
HashMap<>();
PriorityQueue pq = 
new 
PriorityQueue<>();
pq.offer(
new 
DijkstraNode(first, 0));
Первый.узел,.помещенный.в.очередь.с.приоритетом,.содержит.корневую.вершину.
while 
(!pq.isEmpty()) {
int 
u = pq.poll().vertex; // исследовать ближайшую вершину
double 
distU = distances[u]; // это мы уже, должно быть, видели
Мы.будем.выполнять.алгоритм.Дейкстры.до.тех.пор,.пока.очередь.с.при-
оритетом.не.опустеет..
U
.—.текущая.вершина,.с.которой.начинается.поиск,.

---

4.5. Поиск кратчайших путей во взвешенном графе
133
а.
distU
.—.сохраненное.расстояние,.позволяющее.добраться.до.
U
.по.известным.
маршрутам..Все.вершины,.исследованные.на.этом.этапе,.уже.найдены,.поэтому.
для.них.расстояния.уже.известны.
// рассмотреть все ребра и вершины для данной вершины