1. Общ преглед
Акцентът в тази статия е проблемът с най-краткия път (SPP), който е един от основните теоретични проблеми, известни в теорията на графовете, и как алгоритъмът Dijkstra може да бъде използван за решаването му.
Основната цел на алгоритъма е да определи най-краткия път между начален възел и останалата част от графиката.
2. Най-кратък проблем с пътя с Dijkstra
Като се има предвид положително претеглена графика и начален възел (A), Dijkstra определя най-краткия път и разстоянието от източника до всички дестинации в графиката:
Основната идея на алгоритъма Dijkstra е непрекъснатото премахване на по-дълги пътища между началния възел и всички възможни дестинации.
За да следим процеса, трябва да имаме два различни набора от възли, уредени и неуредени.
Уредените възли са тези с известно минимално разстояние от източника. Комплектът неустановени възли събира възли, до които можем да достигнем от източника, но не знаем минималното разстояние от началния възел.
Ето списък на стъпките, които трябва да следвате, за да разрешите SPP с Dijkstra:
- Задайте разстояние на 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 | A | Б. | ° С | д | Е. | F |
|---|---|---|---|---|---|---|---|---|---|
| 1 | A | - | A | 0 | А-10 | А-15 | X-∞ | X-∞ | X-∞ |
| 2 | B, C | A | Б. | 0 | А-10 | А-15 | B-22 | X-∞ | B-25 |
| 3 | C, F, D | А, Б | ° С | 0 | А-10 | А-15 | B-22 | С-25 | B-25 |
| 4 | D, E, F | A, B, C | д | 0 | А-10 | А-15 | B-22 | D-24 | D-23 |
| 5 | E, F | A, B, C, D | F | 0 | А-10 | А-15 | B-22 | D-24 | D-23 |
| 6 | Е. | A, B, C, D, F | Е. | 0 | А-10 | А-15 | B-22 | D-24 | D-23 |
| Финал | - | ВСИЧКО | НИТО ЕДИН | 0 | А-10 | А-15 | B-22 | D-24 | D-23 |
Нотацията B-22, например, означава, че възел B е непосредственият предшественик, с общо разстояние 22 от възел 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); След изчисляване, атрибутите shortestPath и distance се задават за всеки възел в графиката, можем да ги повторим, за да проверим дали резултатите съвпадат точно с това, което е намерено в предишния раздел.
4. Заключение
В тази статия видяхме как алгоритъмът Dijkstra решава SPP и как да го приложим в Java.
Изпълнението на този прост проект може да бъде намерено в следната връзка към проекта GitHub.