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

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

 

다익스트라 구현하기

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

 

다익스트라 알고리즘 순서

1. distance 배열을 MAX_VALUE로 초기화한다.
2. 시작노드의 거리는 0으로 표시하고, 시작노드의 check 값을 true로 바꿔준다.
3. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신한다.
4. 방문하지 않은 노드 중 distance 값이 최소인 min_node를 찾는다.
5. 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

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<Node> {
		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<Node>[] 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<Node>();
		
		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("\n");
			else sb.append(distance[i]).append("\n");
		}
		
		System.out.println(sb);
		
	}
	
	public static void Dijkstra(int K) {
		
		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		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) 참고 사이트

• 자바로 만드는 다익스트라 (dijkstra) 알고리즘
• [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘