1. Обзор
Акцент в этой статье делается на задаче о кратчайшем пути (SPP), являющейся одной из фундаментальных теоретических проблем, известных в теории графов, и на том, как алгоритм Дейкстры может быть использован для ее решения.
Основная цель алгоритма — определить кратчайший путь между начальным узлом и остальной частью графа.
2. Задача о кратчайшем пути с Дейкстрой
Учитывая положительно взвешенный граф и начальный узел (A), Дейкстра определяет кратчайший путь и расстояние от источника до всех пунктов назначения в графе:
Основная идея алгоритма Дейкстры состоит в том, чтобы постоянно исключать более длинные пути между начальным узлом и всеми возможными пунктами назначения.
Чтобы отслеживать процесс, нам нужно иметь два различных набора узлов, установленные и неустановленные.
Оседлые узлы — это узлы с известным минимальным расстоянием от источника. Набор неустановленных узлов собирает узлы, до которых мы можем добраться из источника, но мы не знаем минимального расстояния от начального узла.
Вот список шагов, которые нужно выполнить, чтобы решить SPP с Дейкстрой:
Установите расстояние до
startNodeравным нулю.Установите для всех остальных расстояний бесконечное значение.
Мы добавляем
startNodeв набор неустановленных узлов.Пока набор неустановленных узлов не пуст, мы:
Выберите узел оценки из набора неустановленных узлов, узел оценки должен быть с наименьшим расстоянием от источника.
Рассчитайте новые расстояния до прямых соседей, сохраняя наименьшее расстояние при каждой оценке.
Добавьте соседей, которые еще не установлены, в набор неустановленных узлов.
Эти шаги можно объединить в два этапа: инициализацию и оценку. Давайте посмотрим, как это применимо к нашему примерному графику:
2.1. Инициализация
Прежде чем мы начнем исследовать все пути в графе, нам сначала нужно инициализировать все узлы с бесконечным расстоянием и неизвестным предшественником, кроме источника.
В рамках процесса инициализации нам нужно присвоить значение 0 узлу A (мы знаем, что расстояние от узла A до узла A равно 0)
Таким образом, каждый узел в остальной части графа будет отличаться предшественником и расстоянием:
Чтобы завершить процесс инициализации, нам нужно добавить узел A к неустановленным узлам, чтобы он был выбран первым на этапе оценки. Имейте в виду, набор установленных узлов все еще пуст.
2.2. Оценка
Теперь, когда мы инициализировали наш граф, мы выбираем узел с наименьшим расстоянием из неустановленного набора, затем мы оцениваем все соседние узлы, которые не находятся в установленных узлах:
Идея состоит в том, чтобы добавить вес ребра к расстоянию до узла оценки, а затем сравнить его с расстоянием до пункта назначения. например, для узла B 0+10 меньше, чем БЕСКОНЕЧНОСТЬ, поэтому новое расстояние для узла B равно 10, а новым предшественником является A, то же самое относится к узлу C.
Затем узел А перемещается из набора неустановленных узлов в установленные узлы.
Узлы B и C добавляются к неустановленным узлам, поскольку до них можно добраться, но их необходимо оценить.
Теперь, когда у нас есть два узла в неустановленном наборе, мы выбираем узел с наименьшим расстоянием (узел B), затем повторяем, пока не установим все узлы в графе:
Вот таблица, в которой обобщаются итерации, выполненные на этапах оценки:
| Итерация | Неустроенный | Урегулировано | узел оценки | А | Б | С | Д | Е | Ф |
| 1 | А | – | А | 0 | А-10 | А-15 | Х-∞ | Х-∞ | Х-∞ |
| 2 | ДО Н.Э | А | Б | 0 | А-10 | А-15 | Б-22 | Х-∞ | Б-25 |
| 3 | С, Ф, Д | А, Б | С | 0 | А-10 | А-15 | Б-22 | С-25 | Б-25 |
| 4 | Д, Э, Ф | А, Б, С | Д | 0 | А-10 | А-15 | Б-22 | Д-24 | Д-23 |
| 5 | Э, Ф | А, Б, В, Г | Ф | 0 | А-10 | А-15 | Б-22 | Д-24 | Д-23 |
| 6 | Е | А, Б, В, Г, Ф | Е | 0 | А-10 | А-15 | Б-22 | Д-24 | Д-23 |
| **Финал** | **–** | **ВСЕ** | **НИКТО** | **0** | **А-10** | **А-15** | **Б-22** | **Д-24** | **Д-23** |
Обозначение B-22, например, означает, что узел B является непосредственным предшественником с общим расстоянием 22 от узла A.
Наконец, мы можем вычислить кратчайшие пути из узла A следующим образом:
- Узел B : A -> B (общее расстояние = 10)
- Узел C : A -> C (общее расстояние = 15)
- Узел D: A -> B -> D (общее расстояние = 22)
- Узел E : A -> B -> D -> E (общее расстояние = 24)
- Узел F : A -> B -> D -> F (общее расстояние = 23)
3. Реализация Java
В этой простой реализации мы будем представлять граф как набор узлов:
public class Graph {
private Set<Node> nodes = new HashSet<>();
public void addNode(Node nodeA) {
nodes.add(nodeA);
}
// getters and setters
}
Узел может быть описан с помощью имени , LinkedList относительно кратчайшего пути , расстояния от источника и списка смежности с именем смежных узлов :
public class Node {
private String name;
private List<Node> shortestPath = new LinkedList<>();
private Integer distance = Integer.MAX_VALUE;
Map<Node, Integer> adjacentNodes = new HashMap<>();
public void addDestination(Node destination, int distance) {
adjacentNodes.put(destination, distance);
}
public Node(String name) {
this.name = name;
}
// getters and setters
}
Атрибут смежных узлов используется для связывания непосредственных соседей с длиной ребра. Это упрощенная реализация списка смежности, которая больше подходит для алгоритма Дейкстры, чем для матрицы смежности.
Что касается атрибута shortestPath , то это список узлов, описывающий кратчайший путь, рассчитанный от начального узла.
По умолчанию все расстояния между узлами инициализируются с помощью Integer.MAX_VALUE для имитации бесконечного расстояния, как описано на этапе инициализации.
Теперь давайте реализуем алгоритм Дейкстры:
public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
source.setDistance(0);
Set<Node> settledNodes = new HashSet<>();
Set<Node> unsettledNodes = new HashSet<>();
unsettledNodes.add(source);
while (unsettledNodes.size() != 0) {
Node currentNode = getLowestDistanceNode(unsettledNodes);
unsettledNodes.remove(currentNode);
for (Entry < Node, Integer> adjacencyPair:
currentNode.getAdjacentNodes().entrySet()) {
Node adjacentNode = adjacencyPair.getKey();
Integer edgeWeight = adjacencyPair.getValue();
if (!settledNodes.contains(adjacentNode)) {
calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
unsettledNodes.add(adjacentNode);
}
}
settledNodes.add(currentNode);
}
return graph;
}
Метод getLowestDistanceNode() возвращает узел с наименьшим расстоянием от набора неустановленных узлов, а метод calculateMinimumDistance() сравнивает фактическое расстояние с вновь рассчитанным при следовании по вновь исследованному пути:
private static Node getLowestDistanceNode(Set < Node > unsettledNodes) {
Node lowestDistanceNode = null;
int lowestDistance = Integer.MAX_VALUE;
for (Node node: unsettledNodes) {
int nodeDistance = node.getDistance();
if (nodeDistance < lowestDistance) {
lowestDistance = nodeDistance;
lowestDistanceNode = node;
}
}
return lowestDistanceNode;
}
private static void CalculateMinimumDistance(Node evaluationNode,
Integer edgeWeigh, Node sourceNode) {
Integer sourceDistance = sourceNode.getDistance();
if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
evaluationNode.setDistance(sourceDistance + edgeWeigh);
LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
shortestPath.add(sourceNode);
evaluationNode.setShortestPath(shortestPath);
}
}
Теперь, когда все необходимое готово, давайте применим алгоритм Дейкстры к образцу графа, являющемуся предметом статьи:
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
nodeA.addDestination(nodeB, 10);
nodeA.addDestination(nodeC, 15);
nodeB.addDestination(nodeD, 12);
nodeB.addDestination(nodeF, 15);
nodeC.addDestination(nodeE, 10);
nodeD.addDestination(nodeE, 2);
nodeD.addDestination(nodeF, 1);
nodeF.addDestination(nodeE, 5);
Graph graph = new Graph();
graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);
graph.addNode(nodeE);
graph.addNode(nodeF);
graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA);
После расчета атрибуты shortestPath и Distance устанавливаются для каждого узла в графе, мы можем перебирать их, чтобы убедиться, что результаты точно совпадают с тем, что было найдено в предыдущем разделе.
4. Вывод
В этой статье мы увидели, как алгоритм Дейкстры решает SPP и как его реализовать на Java.
Реализацию этого простого проекта можно найти по следующей ссылке на проект GitHub .