최단경로 / 다익스트라(Dijkstra)

최단경로 / 다익스트라(Dijkstra)

: 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때에 최단경로를 찾는 알고리즘

다익스트라 구현하기

최단 거리 저장 배열 : distance - 각 노드까지의 최단거리가 저장되며, 처음에는 MAX_VALUE로 초기화한다.

방문 확인 배열 : check - 각 노드에 방문했는지를 확인한다.

다익스트라 알고리즘 순서

distance 배열을 MAX_VALUE로 초기화한다. 시작노드의 거리는 0으로 표시하고, 시작노드의 check 값을 true로 바꿔준다. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신한다. 방문하지 않은 노드 중 distance 값이 최소인 min_node를 찾는다. min_node의 check 값을 true로 바꾸고, min_node와 연결된, 방문하지 않은 노드의 distance 값을 갱신한다. 이 때, min_node와 연결된 distance의 값이 distance[min_node] + (min_node와 그 노드의 거리)보다 큰 경우에는 distance 값을 distance[min_node] + (min_node와 그 노드의 거리) 로 갱신한다.

다익스트라 구현

public class Main { public static int V, E, K; // V : 정점의 개수, E : 간선의 개수, K : 시작정점의 번호 public static int[][] weight; // 가중치 배열 public static int[] distance; // 최단거리 저장 배열 public static boolean[] check; // 방문체크용 배열 public static void main(String[] args) { // V, E, K 입력받음 weight = new int[V+1][V+1]; check = new boolean[V+1]; distance = new int[V+1]; for(int i = 1; i < V+1; i++) for(int j = 1; j < V+1; j++) weight[i][j] = Integer.MAX_VALUE for(int i = 0; i < E; i++) { // weight[][]를 입력받음 // 양방향의 경우에는 weight[a][b] = weight[b][a] = c // 단방향의 경우에는 weight[a][b] = c } Arrays.fill(distance, Integer.MAX_VALUE); distance[K] = 0; for(int i = 0; i < V-1; i++) { int min = Integer.MAX_VALUE; int index = 1; for(int j = 1; j < V+1; j++) if(!check[j] && min > distance[j]) { index = j; min = distance[j]; } check[index] = true; for(int j = 1; j < V+1; j++) if(!check[j] && weight[index][j] != Integer.MAX_VALUE && distance[j] > distance[index] + weight[index][j]) distance[j] = distance[index] + weight[index][j]; } } }

다익스트라 알고리즘 코드

출처 : https://www.acmicpc.net/problem/1753

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; import java.util.Arrays; import java.util.ArrayList; import java.util.PriorityQueue; public class Main { public static class Node implements Comparable { int end; int weight; public Node(int end, int weight) { this.end = end; this.weight = weight; } @Override public int compareTo(Node n) { return this.weight - n.weight; } } public static int V, E, K; public static final int INF = Integer.MAX_VALUE; public static ArrayList[] weight; public static int[] distance; public static boolean[] check; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int V = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(br.readLine()); weight = new ArrayList[V + 1]; for(int i = 1; i < V + 1; i++) weight[i] = new ArrayList(); distance = new int[V+1]; check = new boolean[V+1]; Arrays.fill(distance, INF); for(int i = 0; i < E; i++) { st = new StringTokenizer(br.readLine(), " "); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); weight[u].add(new Node(v, w)); } Dijkstra(K); StringBuilder sb = new StringBuilder(); for(int i = 1; i < V+1; i++) { if(distance[i] == INF) sb.append("INF").append("

"); else sb.append(distance[i]).append("

"); } System.out.println(sb); } public static void Dijkstra(int K) { PriorityQueue queue = new PriorityQueue(); queue.offer(new Node(K, 0)); distance[K] = 0; while(!queue.isEmpty()) { Node node = queue.poll(); int cur = node.end; if(check[cur] == true) continue; check[cur] = true; for(Node n : weight[cur]) { if(distance[n.end] > distance[cur] + n.weight) { distance[n.end] = distance[cur] + n.weight; queue.offer(new Node(n.end, distance[n.end])); } } } } }

최단경로 / 다익스트라(Dijkstra) 참고 사이트

from http://se0r1-tae27.tistory.com/100 by ccl(A) rewrite - 2021-09-24 19:26:54