|
| 1 | +package dijkstras_algorithm; |
| 2 | + |
| 3 | +import java.util.ArrayList; |
| 4 | +import java.util.HashMap; |
| 5 | +import java.util.List; |
| 6 | +import java.util.Map; |
| 7 | + |
| 8 | +public class DijkstraAlgorithm { |
| 9 | + // Граф |
| 10 | + private static Map<String, Map<String, Double>> graph = new HashMap<>(); |
| 11 | + |
| 12 | + // Список отслеживания всех уже обработанных узлов |
| 13 | + private static List<String> processed = new ArrayList<>(); |
| 14 | + |
| 15 | + |
| 16 | + public static void main(String[] args) { |
| 17 | + graph.put("start", new HashMap<>()); |
| 18 | + |
| 19 | + // Одно ребро ведет из начального узла в А, а |
| 20 | + // другое - из начального узла в В. |
| 21 | + graph.get("start").put("a", 6.0); |
| 22 | + graph.get("start").put("b", 2.0); |
| 23 | + |
| 24 | + graph.put("a", new HashMap<>()); |
| 25 | + graph.get("a").put("fin", 1.0); |
| 26 | + |
| 27 | + graph.put("b", new HashMap<>()); |
| 28 | + graph.get("b").put("a", 3.0); |
| 29 | + graph.get("b").put("fin", 5.0); |
| 30 | + |
| 31 | + // У конечного узла нет соседей |
| 32 | + graph.put("fin", new HashMap<>()); |
| 33 | + |
| 34 | + // Хеш-таблица для хранения стоимостей узлов |
| 35 | + Map<String, Double> costs = new HashMap<>(); |
| 36 | + costs.put("a", 6.0); |
| 37 | + costs.put("b", 2.0); |
| 38 | + // Стоимость неизвестна, поэтому она считается бесконечной |
| 39 | + costs.put("fin", Double.POSITIVE_INFINITY); |
| 40 | + |
| 41 | + // Хеш-таблица родителей |
| 42 | + Map<String, String> parents = new HashMap<>(); |
| 43 | + parents.put("a", "start"); |
| 44 | + parents.put("b", "start"); |
| 45 | + parents.put("fin", null); |
| 46 | + |
| 47 | + // Найти узел с наименьшей стоимостью среди необработанных |
| 48 | + String node = findLowestCostNode(costs); |
| 49 | + |
| 50 | + while (node != null) { |
| 51 | + Double cost = costs.get(node); |
| 52 | + Map<String, Double> neighbors = graph.get(node); |
| 53 | + |
| 54 | + // Перебрать всех соседей текущего узла |
| 55 | + for (String n : neighbors.keySet()) { |
| 56 | + |
| 57 | + double newCost = cost + neighbors.get(n); |
| 58 | + // Если к соседу можно быстрее |
| 59 | + // добраться через текущий узел ... |
| 60 | + if (costs.get(n) > newCost) { |
| 61 | + // ... обновить стоимость для этого узла |
| 62 | + costs.put(n, newCost); |
| 63 | + |
| 64 | + // Этот узел становится новым родителем для соседа |
| 65 | + parents.put(n, node); |
| 66 | + } |
| 67 | + } |
| 68 | + // Узел помечается как обработанный |
| 69 | + processed.add(node); |
| 70 | + |
| 71 | + // Найти следующий узел для обработки и повторить |
| 72 | + // цикл |
| 73 | + node = findLowestCostNode(costs); |
| 74 | + } |
| 75 | + |
| 76 | + System.out.println("Cost from the start to each node:"); |
| 77 | + System.out.println(costs); // { a: 5, b: 2, fin: 6 } |
| 78 | + |
| 79 | + } |
| 80 | + |
| 81 | + private static String findLowestCostNode(Map<String, Double> costs) { |
| 82 | + Double lowestCost = Double.POSITIVE_INFINITY; |
| 83 | + String lowestCostNode = null; |
| 84 | + |
| 85 | + // Перебрать все узлы |
| 86 | + for (Map.Entry<String, Double> node : costs.entrySet()) { |
| 87 | + Double cost = node.getValue(); |
| 88 | + // Если это узел с наименьшей стоимостью |
| 89 | + // из уже виденных и он еще не был обработан... |
| 90 | + if (cost < lowestCost && !processed.contains(node.getKey())) { |
| 91 | + // ... он назначается новым узлом |
| 92 | + // с наименьшей стоимостью |
| 93 | + lowestCost = cost; |
| 94 | + lowestCostNode = node.getKey(); |
| 95 | + } |
| 96 | + } |
| 97 | + |
| 98 | + return lowestCostNode; |
| 99 | + } |
| 100 | +} |
0 commit comments