Java의 Dijkstra 최단 경로 알고리즘

1. 개요

이 기사에서 강조하는 것은 그래프 이론에서 알려진 근본적인 이론적 문제 중 하나 인 최단 경로 문제 (SPP)와이를 해결하기 위해 Dijkstra 알고리즘을 사용하는 방법입니다.

알고리즘의 기본 목표는 시작 노드와 나머지 그래프 사이의 최단 경로를 결정하는 것입니다.

2. Dijkstra의 최단 경로 문제

양의 가중치 그래프와 시작 노드 (A)가 주어지면 Dijkstra는 소스에서 그래프의 모든 대상까지의 최단 경로와 거리를 결정합니다.

Dijkstra 알고리즘의 핵심 아이디어는 시작 노드와 가능한 모든 대상 사이의 긴 경로를 지속적으로 제거하는 것입니다.

프로세스를 추적하려면 두 개의 별개의 노드 세트 (안정 및 미정)가 필요합니다.

정착 노드는 소스에서 최소 거리가 알려진 노드입니다. 설정되지 않은 노드 집합은 소스에서 도달 할 수있는 노드를 수집하지만 시작 노드로부터의 최소 거리를 모릅니다.

다음은 Dijkstra로 SPP를 해결하기 위해 따라야 할 단계 목록입니다.

  • startNode에 대한 거리를 0으로 설정 합니다.
  • 다른 모든 거리는 무한 값으로 설정하십시오.
  • unsettled 노드 세트에 startNode 를 추가합니다 .
  • 설정되지 않은 노드 세트는 비어 있지 않지만 다음을 수행합니다.
    • 설정되지 않은 노드 집합에서 평가 노드를 선택합니다. 평가 노드는 소스에서 가장 가까운 거리에있는 노드 여야합니다.
    • 각 평가에서 가장 낮은 거리를 유지하여 직접 이웃과의 새로운 거리를 계산합니다.
    • 아직 정착되지 않은 이웃을 미결정 노드 세트에 추가합니다.

이러한 단계는 초기화 및 평가의 두 단계로 집계 할 수 있습니다. 이것이 샘플 그래프에 어떻게 적용되는지 살펴 보겠습니다.

2.1. 초기화

그래프의 모든 경로를 탐색하기 전에 먼저 소스를 제외하고 무한한 거리와 알 수없는 선행 노드로 모든 노드를 초기화해야합니다.

초기화 프로세스의 일부로 노드 A에 값 0을 할당해야합니다 (노드 A에서 노드 A까지의 거리가 분명히 0이라는 것을 알고 있습니다).

따라서 나머지 그래프의 각 노드는 전임자와 거리로 구분됩니다.

초기화 프로세스를 완료하려면 평가 단계에서 먼저 선택되도록 설정되지 않은 노드에 노드 A를 추가해야합니다. 정산 된 노드 세트는 여전히 비어 있습니다.

2.2. 평가

이제 그래프가 초기화되었으므로 불안정한 집합에서 가장 낮은 거리를 가진 노드를 선택한 다음 정착 된 노드에없는 모든 인접 노드를 평가합니다.

아이디어는 평가 노드 거리에 가장자리 가중치를 추가 한 다음 목적지의 거리와 비교하는 것입니다. 예를 들어 노드 B의 경우 0 + 10이 INFINITY보다 낮으므로 노드 B의 새 거리는 10이고 새 선행 작업은 A이며 노드 C에도 동일하게 적용됩니다.

그런 다음 노드 A는 설정되지 않은 노드 집합에서 정착 된 노드로 이동됩니다.

노드 B와 C는 도달 할 수 있기 때문에 불안정한 노드에 추가되지만 평가해야합니다.

이제 설정되지 않은 세트에 두 개의 노드가 있으므로 거리가 가장 낮은 노드 (노드 B)를 선택한 다음 그래프의 모든 노드를 설정할 때까지 반복합니다.

다음은 평가 단계에서 수행 된 반복을 요약 한 표입니다.

되풀이 변하기 쉬운 안정된 EvaluationNode 이자형 에프
1 0 A-10 A-15 X-∞ X-∞ X-∞
2 B, C 0 A-10 A-15 B-22 X-∞ B-25
C, F, D A, B 0 A-10 A-15 B-22 C-25 B-25
4 D, E, F A, B, C 0 A-10 A-15 B-22 D-24 D-23
5 E, F A, B, C, D 에프 0 A-10 A-15 B-22 D-24 D-23
6 이자형 A, B, C, D, F 이자형 0 A-10 A-15 B-22 D-24 D-23
결정적인 모두 없음 0 A-10 A-15 B-22 D-24 D-23

예를 들어, 표기법 B-22는 노드 B가 노드 A로부터 총 거리가 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. 자바 구현

이 간단한 구현에서는 그래프를 노드 집합으로 표현합니다.

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

계산 후, 그래프의 각 노드에 대해 shortestPathdistance 속성이 설정되고,이를 반복하여 결과가 이전 섹션에서 찾은 것과 정확히 일치하는지 확인할 수 있습니다.

4. 결론

이 기사에서는 Dijkstra 알고리즘이 SPP를 해결하는 방법과이를 Java로 구현하는 방법을 살펴 보았습니다.

이 간단한 프로젝트의 구현은 다음 GitHub 프로젝트 링크에서 찾을 수 있습니다.