-
우선 순위 큐를 활용해 개선시킨 다익스크라 알고리즘알고리즘 2022. 6. 28. 15:44
2022.06.27 - [분류 전체보기] - 최단 경로 - 다익스트라 알고리즘
최단 경로를 구하는 알고리즘 중 다익스트라 알고리즘을 위의 링크처럼 간단히 구현하면 O(V^2)의 시간 복잡도가 나오기 때문에 노드 개수가 10000개가 넘어가면 위의 코드로는 구현하기가 힘들다.
따라서 매번 최단 거리 테이블을 선형적으로 탐색하는 것이 아니라 우선순위 큐를 활용하여 찾게 되면 O(ElogV)의 시간 복잡도로 구현할 수 있다.
개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다.
import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class Node implements Comparable<Node> { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance; } @Override public int compareTo(Node node) { if (this.distance < node.distance) return -1; return 1; } } public class Dijkstra_improved { static final int INF = (int) 1e9; static int n,m,start; static ArrayList<ArrayList<Node>> graph = new ArrayList<>(); static int[] table = new int[100001]; public static void dijkstra(int start) { PriorityQueue<Node> pq = new PriorityQueue<>(); pq.offer(new Node(start, 0)); table[start] = 0; while (!pq.isEmpty()) { Node node = pq.poll(); int dist = node.getDistance(); int now = node.getIndex(); if (table[now] < dist) continue; for (int i = 0; i < graph.get(now).size(); i++) { int cost = table[now] + graph.get(now).get(i).getDistance(); if (cost < table[graph.get(now).get(i).getIndex()]) { table[graph.get(now).get(i).getIndex()] = cost; pq.offer(new Node(graph.get(now).get(i).getIndex(), cost)); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); start = sc.nextInt(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<Node>()); } for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); graph.get(a).add(new Node(b, c)); } //테이블을 모두 무한으로 초기화 Arrays.fill(table, INF); dijkstra(start); for (int i = 1; i <= n; i++) { if (table[i] == INF) System.out.println("infinite"); else System.out.println(table[i]); } } }
'알고리즘' 카테고리의 다른 글
위상 정렬 (0) 2022.07.21 플로이드 워셜 알고리즘(자바) (0) 2022.07.11 최단 경로 - 다익스트라 알고리즘 (0) 2022.06.27 Set 과 Map (Hash Set) - 자바 Collection (0) 2022.04.18 크루스칼(kruskal) 알고리즘, 최소 신장 트리(MST) (0) 2022.04.14