Алгоритм кратчайшего пути Дейкстры в Java
Акцент в этой статье делается на задаче о кратчайшем пути (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 SetNode> nodes = new HashSet>(); public void addNode(Node nodeA) nodes.add(nodeA); > // getters and setters > Узел может быть описан с помощью имени , LinkedList относительно кратчайшего пути , расстояния от источника и списка смежности с именем смежных узлов :
public class Node private String name; private ListNode> shortestPath = new LinkedList>(); private Integer distance = Integer.MAX_VALUE; MapNode, 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); SetNode> settledNodes = new HashSet>(); SetNode> 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); LinkedListNode> 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 .
Dijkstra’s shortest path algorithm in Java using PriorityQueue
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with a given source as a root. We maintain two sets, one set contains vertices included in the shortest-path tree, other set includes vertices not yet included in the shortest-path tree. At every step of the algorithm, we find a vertex that is in the other set (set of not yet included) and has a minimum distance from the source.
Here the only drawback with Dijkstra algorithms is that while finding the shortest path as listed as follows as we need to find the least cost path by going through the whole cost array. Not a big deal for small graphs and at the same time becomes an efficiency issue for large graphs because each time we need to run through an array while traversing. Now as we know queues can work for us so do we apply the concept of priority queues with this algorithm to erupt out some of the disadvantages and making complexity much better.
Let us now discuss the problem statement whereas in accordance with the title it seems like the sheer implementation of one of the data structures known as priority queue with involvement of algorithm analysis in it. So let us begin with the problem statement which is listed below prior to it do stress over note as the whole concept revolves around the adjacency matrix representation.
Problem statement
Given a graph with adjacency list representation of the edges between the nodes, the task is to implement Dijkstra’s Algorithm for single-source shortest path using Priority Queue in Java. Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.
Illustration:
Input : Source = 0 Output : Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
Implementation:
Java Program for Dijkstra’s shortest path algorithm | Greedy Algo-7
Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph. Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source. Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph. Algorithm 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn’t include all vertices ….a) Pick a vertex u which is not there in sptSet and has minimum distance value. ….b) Include u to sptSet. ….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.