이번에는 다익스트라 알고리즘에 대해 알아보자.
다익스트라 알고리즘은 그래프에서 최단 경로를 찾기 위한 매우 유명한 알고리즘으로, 특히 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 데 사용된다.
다익스트라 알고리즘은 그래프 내에서 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다.
이 알고리즘은 주로 네트워크 경로 최적화, 지도 애플리케이션에서 경로 탐색, 그리고 게임에서 캐릭터의 이동 경로 결정 등에 사용된다.
다익스트라 알고리즘은 다음과 같은 단계로 동작한다:
다익스트라 알고리즘의 시간 복잡도는 사용된 자료구조에 따라 달라진다.
일반적인 구현에서 우선순위 큐를 사용할 경우 O((V + E) log V)이다.
여기서 V는 노드의 수, E는 간선의 수를 의미한다.
아래는 다익스트라 알고리즘을 우선순위 큐(Priority Queue)를 사용해 구현한 예제 코드이다.
이 코드에서는 그래프에서 특정 노드를 시작으로 다른 모든 노드까지의 최단 경로를 계산한다.
import java.util.*;
class Node implements Comparable<Node> {
int vertex;
int weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return this.weight - other.weight;
}
}
public class DijkstraExample {
public static void dijkstra(int start, Map<Integer, List<Node>> graph, int[] distances) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
distances[start] = 0;
while (!pq.isEmpty()) {
Node currentNode = pq.poll();
int currentVertex = currentNode.vertex;
for (Node neighbor : graph.get(currentVertex)) {
int newDist = distances[currentVertex] + neighbor.weight;
if (newDist < distances[neighbor.vertex]) {
distances[neighbor.vertex] = newDist;
pq.add(new Node(neighbor.vertex, newDist));
}
}
}
}
public static void main(String[] args) {
Map<Integer, List<Node>> graph = new HashMap<>();
graph.put(1, Arrays.asList(new Node(2, 2), new Node(3, 4)));
graph.put(2, Arrays.asList(new Node(3, 1), new Node(4, 7)));
graph.put(3, Arrays.asList(new Node(5, 3)));
graph.put(4, Arrays.asList(new Node(5, 1)));
graph.put(5, new ArrayList<>());
int[] distances = new int[6];
Arrays.fill(distances, Integer.MAX_VALUE);
dijkstra(1, graph, distances);
for (int i = 1; i < distances.length; i++) {
System.out.println("Distance from 1 to " + i + " is " + distances[i]);
}
}
}