[알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘(데이크스트라)

그래프에서 어떠한 점(A)에서 어떠한 점(B)으로 가는 최단 거리를 구할 때 사용하는 알고리즘입니다.

 

 

핵심

1. 다익스트라는 BFS의 확장 같은 느낌.(현재 점에서 연결되어 있는 모든 점 검사,,, 그러나 이미 거리가 확정된 곳은 제외)

 

2.거리 배열을 하나 만들어서 각 점을 할당한다.

각 배열이 의미하는 바는 시작지점에서 해당 지점까지 얼마나 걸리는지 기록.

 

3.가중치에 음수가 있다면 알고리즘 성립안됨!!

 

설명

(1) S1에서 시작하여, 배열 안 S2,S3 값을 1,5로 초기화합니다.

(2) 현재 위치에서 가까운 S2로 갑니다.

(3) S2에서 S3로 가는데 3의 비용이 듭니다.

 

현재 누적된 S2의 비용(1) + S3로 가는 비용(2)

VS

기존에 있는 S3의 값(S1->S3)

 

을 비교해서 더 작은 값을 S3에 할당합니다.

즉 시작점에서 S3로 가는 최단거리는 3이 됩니다.

다익스트라는 이런식으로 작동합니다.

 

 

코드

import java.util.*;
import java.io.*;
class Vertex implements Comparable<Vertex>{
	int no;
	int minDistance;
	public Vertex(int no, int minDistance) {
		this.no = no;
		this.minDistance = minDistance;
	}
@Override
public int compareTo(Vertex o) {
	// TODO Auto-generated method stub
	return this.minDistance - o.minDistance;
}
}
public class Dijkstra_Tets2PQ {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int V = Integer.parseInt(br.readLine());
		
		//int adjMatrix[][] = new int[V][V];
		ArrayList<Vertex> list[] = new ArrayList[V];
		for(int i=0; i<V; i++) {
			list[i] = new ArrayList<>();
		}
		int start = 0;
		
		StringTokenizer st = null;
		
		for(int i=0; i<V; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<V; j++) {
				//adjMatrix[i][j] = Integer.parseInt(st.nextToken());
				int value = Integer.parseInt(st.nextToken());
				if(value != 0)
				list[i].add(new Vertex(j,value));
			}
		}
		
		int[] distance = new int[V];
		boolean[] visit = new boolean[V];
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		Arrays.fill(distance, (int)10e9);
		distance[start] = 0;
		
		pq.add(new Vertex(start,distance[start]));
		while(!pq.isEmpty()) {
			//단계1 최소비용이 확정되지 않은 정점중 최소비용의 정점 선택
//			int min = (int)10e9,current = 0;
//			for(int j=0; j<V; j++) {
//				if(!visit[j] && min>distance[j]) {
//					min = distance[j];
//					current = j;
//				}
//			}
			Vertex current = pq.poll();
			if(distance[current.no] < current.minDistance) continue;
			//단계2 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지않은 다른정점의 최소비용을 고려ㅕ
			for(int j=0; j<list[current.no].size(); j++) {
				Vertex vertex = list[current.no].get(j);
				if(distance[vertex.no]> current.minDistance + vertex.minDistance) {
					distance[vertex.no] = current.minDistance + vertex.minDistance;
					pq.add(new Vertex(vertex.no,distance[vertex.no]));
				}
			}
		}
		System.out.println(Arrays.toString(distance));
	}

}

코드를 봤을때

핵심 로직은

 

1. 최소비용이 확정되지 않은 정점 중에서, 최소 정점 비용이 드는 곳 선택!

(위 예제의 경우 S1에서 S2,S3를 둘 중 하나를 고르는 과정)

2. 1에서 선택된 점과 연결된 점들을 하나씩 확인하며 최소거리를 계산해서 배열에 넣어줌

 

 

++추천문제

1238파티