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

Листинг 4.13. 
WeightedGraph.java (продолжение)
public static final class 
DijkstraNode 
implements 
Comparable {
public final int 
vertex;
public final double 
distance;
public 
DijkstraNode(
int 
vertex, 
double 
distance) {
this
.vertex = vertex;
this
.distance = distance;
}
@Override
public int 
compareTo(DijkstraNode other) {
Double mine = distance;
Double theirs = other.distance;

---

4.5. Поиск кратчайших путей во взвешенном графе
131
 
return 
mine.compareTo(theirs);
}
}
public static final class 
DijkstraResult {
public final double
[] distances;
public final 
Map pathMap;
public 
DijkstraResult(
double
[] distances, Map
pathMap) {
this
.distances = distances;
this
.pathMap = pathMap;
}
}
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]; // это мы уже, должно быть, видели
// все ребра и вершины для данной вершины
for 
(WeightedEdge we : edgesOf(u)) {
// старое расстояние до этой вершины
double 
distV = distances[we.v];
// новое расстояние до этой вершины
double 
pathWeight = we.weight + distU;
// новая вершина или найден более короткий путь?
if 
(!visited[we.v] || (distV > pathWeight)) {
visited[we.v] = 
true
;
// изменить расстояние до этой вершины 
distances[we.v] = pathWeight;
// заменить ребро на более короткий путь к этой вершине
pathMap.put(we.v, we);
// вскоре мы это проверим
pq.offer(
new 
DijkstraNode(we.v, pathWeight));
}
}
}
 return new 
DijkstraResult(distances, pathMap);
}
// Вспомогательная функция для получения удобного доступа
// к результатам алгоритма Дейкстры
public 
Map distanceArrayToDistanceMap(
double
[] distances) {

---

132
Глава 4.
Графовые задачи
HashMap distanceMap = 
new 
HashMap<>();
for 
(
int 
i = 0; i < distances.length; i++) {
distanceMap.put(vertexAt(i), distances[i]);
}
return 
distanceMap;
}
// Принимает словарь ребер, позволяющих достичь каждого узла, 
// и возвращает список ребер от start до end
public static 
List pathMapToPath(
int 
start, 
int 
end,
Map pathMap) {