다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘?

 - 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.

 - 도착 정점 뿐만 아니라 다른 모든 정점까지의 최단 경로도 구할 수 있다.

 - 간선 가중치가 양수인 경우에만 사용할 수 있다.

   -> (음수 가중치를 고려해야 하는 경우 벨만-포드, 플로이드-워셜 알고리즘 사용)

 

수행 과정

  1. 시작 정점과 끝 정점 설정.

  2. 현재 정점과 연결된 정점 중 방문하지 않았고, 간선 가중치가 가장 작은 정점을 선택.

  3. 선택된 정점을 기준으로 간선 비용을 계산하여 최단 거리 테이블에 기록.

  4. 2와 3의 과정을 반복하여 끝 정점까지의 비용을 모두 계산

 

 

구현

BOJ 1753 최단 경로 

 

1. 각 정점간 방문 및 최단 거리를 확인할 배열을 선언.

2. 연결된 정점 중 간선 가중치가 가장 작은 간선을 선택하기 위해 우선순위 큐 사용.

 

3. 자기 자신과의 거리는 계산하지 않는다.

4. 우선 순위 큐에서 가중치가 가장 작은 간선을 선택하고, 모든 정점과의 거리를 연산할 때까지 반복하여 비교 연산 수행.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int v, e, k;
	static List<Node>[] nodeList;
	static class Node implements Comparable<Node>{
		int to;
		int weight;
		public Node(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return this.weight-o.weight;
		}
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		// 정점의 개수 v
		v = Integer.parseInt(st.nextToken());
		// 간선의 개수 e
		e = Integer.parseInt(st.nextToken());
		// 시작 정점 k
		k = Integer.parseInt(br.readLine());
		
		// 정점 연결 정보를 저장할 List[]
		nodeList = new ArrayList[v+1];
		
		for(int i=1; i<=v; i++) {
			nodeList[i] = new ArrayList<>();
		}
		
		for(int i=0; i<e; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			nodeList[from].add(new Node(to, weight));
		}
		
		// 방문체크 visit[]
		boolean[] visit = new boolean[v+1];
		// 최단거리 기록할 distance[]
		int[] distance = new int[v+1];
		
		// 최소 간선 가중치를 선택하기 위해 우선순위 큐 사용.
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(k, 0));
		
		// 간선 비용 비교하기 위해.
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		// 정점 자신과의 거리는 계산하지 않음.
		distance[k] = 0;
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			//방문했던 정점을 제외하기 위해 방문 체크
			if(visit[cur.to]) continue;
			visit[cur.to] = true;
			
			// 현재 정점과 연결된 모든 정점 탐색
			for(Node n : nodeList[cur.to]) {
				// distance에 기록되어 있는 다음 정점까지의 최소 가중치 합보다
				// 현재 정점까지의 가중치 + 현재 정점과 다음 정점간 가중치 합이 더 작다면
				if(distance[n.to]> distance[cur.to]+n.weight) {
					//가중치 갱신
					distance[n.to] = distance[cur.to]+n.weight;
					pq.add(new Node(n.to, distance[n.to]));
				}
			}
		}
		for(int i=1; i<=v; i++) {
			sb.append(distance[i]==Integer.MAX_VALUE ? "INF" : distance[i]).append("\n");
		}
		System.out.println(sb.toString());
	}

}