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

134
Глава 4.
Графовые задачи
Map nameDistance = 
cityGraph2.distanceArrayToDistanceMap(dijkstraResult.distances);
System.
out
.println("Distances from Los Angeles:");
nameDistance.forEach((name, distance) -> System.
out
.println(name + " : " + 
distance));
System.
out
.println(); // пустая строка
System.
out
.println("Shortest path from Los Angeles to Boston:");
List path = 
pathMapToPath
(cityGraph2.indexOf("Los Angeles"),
cityGraph2.indexOf("Boston"), dijkstraResult.pathMap);
cityGraph2.printWeightedPath(path);
Результат.должен.выглядеть.примерно.так:
Distances from Los Angeles:
New York : 2474.0
Detroit : 1992.0
Seattle : 1026.0
Chicago : 1754.0
Washington : 2388.0
Miami : 2340.0
San Francisco : 348.0
Atlanta : 1965.0
Phoenix : 357.0
Los Angeles : 0.0
Dallas : 1244.0
Philadelphia : 2511.0
Riverside : 50.0
Boston : 2605.0
Houston : 1372.0
Shortest path from Los Angeles to Boston:
Los Angeles 50.0> Riverside
Riverside 1704.0> Chicago
Chicago 238.0> Detroit
Detroit 613.0> Boston
Total Weight: 2605.0
Возможно,.вы.заметили,.что.у.алгоритма.Дейкстры.есть.некоторое.сходство.
с.алгоритмом.Ярника..Оба.они.жадные,.и.при.желании.их.можно.реализовать,.
используя.довольно.похожий.код..Другой.алгоритм,.похожий.на.алгоритм.Дейк-
стры,.—.это.A*.из.главы.2..A*.можно.рассматривать.как.модификацию.алгоритма.
Дейкстры..Добавьте.эвристику.и.ограничьте.алгоритм.Дейкстры.поиском.только.
одного.пункта.назначения.—.и.оба.алгоритма.окажутся.одинаковыми.
ПРИМЕЧАНИЕ
Алгоритм.Дейкстры.предназначен.для.графов.с.положительными.весами..Графы.с.от-
рицательно.взвешенными.ребрами.могут.создать.проблему.и.потребуют.модификации.
или.альтернативного.алгоритма.

---

4.7. Упражнения