Алгоритм кратчайшего пути Дейкстры в Java

1. Обзор

Основное внимание в этой статье уделяется задаче кратчайшего пути (SPP), являющейся одной из фундаментальных теоретических проблем, известных в теории графов, и тому, как алгоритм Дейкстры может быть использован для ее решения.

Основная цель алгоритма - определить кратчайший путь между начальным узлом и остальной частью графа.

2. Задача кратчайшего пути с помощью Дейкстры

Учитывая положительно взвешенный граф и начальный узел (A), Дейкстра определяет кратчайший путь и расстояние от источника до всех пунктов назначения в графе:

Основная идея алгоритма Дейкстры состоит в том, чтобы постоянно устранять более длинные пути между начальным узлом и всеми возможными пунктами назначения.

Чтобы отслеживать процесс, нам нужно иметь два различных набора узлов: устойчивые и неустановленные.

Установленные узлы - это узлы с известным минимальным расстоянием от источника. Набор неустановленных узлов собирает узлы, которых мы можем достичь от источника, но мы не знаем минимального расстояния от начального узла.

Вот список шагов, которые нужно выполнить, чтобы решить SPP с помощью Дейкстры:

  • Установите расстояние до startNode равным нулю.
  • Установите все остальные расстояния на бесконечное значение.
  • Мы добавляем startNode в набор неустановленных узлов.
  • Пока набор неустановленных узлов не пустой, мы:
    • Выберите узел оценки из набора невыполненных узлов, узел оценки должен быть узлом с наименьшим расстоянием от источника.
    • Вычисляйте новые расстояния до прямых соседей, сохраняя наименьшее расстояние при каждой оценке.
    • Добавьте соседей, которые еще не урегулированы, к набору невыполненных узлов.

Эти шаги можно объединить в два этапа: инициализация и оценка. Давайте посмотрим, как это применимо к нашему образцу графика:

2.1. Инициализация

Прежде чем мы начнем исследовать все пути в графе, нам сначала нужно инициализировать все узлы с бесконечным расстоянием и неизвестным предшественником, кроме источника.

В рамках процесса инициализации нам нужно присвоить значение 0 узлу A (мы знаем, что расстояние от узла A до узла A, очевидно, равно 0)

Итак, каждый узел в остальной части графа будет отличаться своим предшественником и расстоянием:

Чтобы завершить процесс инициализации, нам нужно добавить узел A к неустановленным узлам, чтобы он был выбран первым на этапе оценки. Имейте в виду, что установленный набор узлов все еще пуст.

2.2. Оценка

Теперь, когда наш граф инициализирован, мы выбираем узел с наименьшим расстоянием от неустановленного множества, затем оцениваем все соседние узлы, которые не находятся в установленных узлах:

Идея состоит в том, чтобы добавить вес ребра к расстоянию оценочного узла, а затем сравнить его с расстоянием до места назначения. например, для узла B, 0 + 10 меньше, чем INFINITY, поэтому новое расстояние для узла B равно 10, а новый предшественник - A, то же самое относится к узлу C.

Затем узел A перемещается из набора невыполненных узлов в установленные узлы.

Узлы B и C добавляются к неустановленным узлам, потому что они могут быть достигнуты, но их необходимо оценить.

Теперь, когда у нас есть два узла в неустановленном множестве, мы выбираем тот, у которого наименьшее расстояние (узел B), затем повторяем, пока не установим все узлы в графе:

Вот таблица, в которой перечислены итерации, которые были выполнены на этапах оценки:

Итерация Неурегулированный Поселился EvaluationNode А B C D E F
1 А - А 0 А-10 А-15 X-∞ X-∞ X-∞
2 ДО Н.Э А B 0 А-10 А-15 В-22 X-∞ В-25
3 C, F, D А, Б C 0 А-10 А-15 В-22 С-25 В-25
4 D, E, F А, Б, В D 0 А-10 А-15 В-22 D-24 D-23
5 E, F А, Б, В, D F 0 А-10 А-15 В-22 D-24 D-23
6 E A, B, C, D, F E 0 А-10 А-15 В-22 D-24 D-23
Финал - ВСЕ НИКТО 0 А-10 А-15 В-22 D-24 D-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 nodes = new HashSet(); public void addNode(Node nodeA) { nodes.add(nodeA); } // getters and setters }

A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:

public class Node { private String name; private List shortestPath = new LinkedList(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } // getters and setters }

The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.

As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.

By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.

Now, let's implement the Dijkstra algorithm:

public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(0); Set settledNodes = new HashSet(); Set unsettledNodes = new HashSet(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry  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; }

The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:

private static Node getLowestDistanceNode(Set  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 shortestPath = new LinkedList(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } }

Now that all the necessary pieces are in place, let's apply the Dijkstra algorithm on the sample graph being the subject of the article:

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); 

После расчета для каждого узла в графе устанавливаются атрибуты shortPath и distance , мы можем перебирать их, чтобы убедиться, что результаты точно соответствуют тому, что было найдено в предыдущем разделе.

4. Вывод

В этой статье мы увидели, как алгоритм Дейкстры решает SPP и как реализовать его на Java.

Реализацию этого простого проекта можно найти по следующей ссылке на проект GitHub.