[알고리즘]그래프5 - 다익스트라(feat. Java)

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

• 그래프의 최단 경로를 구하는 알고리즘
• 하나의 정점에서 출발하는 최단 거리를 구함
• 음수 가중치 X 가정
• 배열로 구현 그래프의 경우 : O(n^2)
• 우선순위 큐 사용 -> O(mlogn)

 

 

 

과정

• 아직 방문하지 않은 정점 중 출발지로부터 가장 거리가 짧은 정점을 방문
• 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신

• pq : 우선순위 큐, 정점과 출발지에서 정점까지 가는 최소 거리를 저장, 거리가 짧을 수록 우선순위 높음
• check : 정점을 방문한지 체크하는 배열
• dist : int 배열로 출발지에서 최소 거리를 기록

 

• 출발지 4를 우선순위 큐에 넣음, 출발지이므로 거리는 0

 

• 우선순위 큐에서 하나 꺼내 nowVertex에 저장하고 방문체크, nowVertex를 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신
• 정점 4와 인접한 정점은 1, 5번 정점
• dist[1] = 8, dist[5] = 3으로 변경 후, pq에 넣어줌 

 

• 우선순위 큐에서 값이 있으므로 꺼내서 nowVertex에 저장
• 정점 5번 방문 체크, 인접 노드는 4,2번 노드
• dist[2]의 값은 기존의 dist[2]의 값과 정점 5를 지나서 정점 2를 가는 dist[5] + 31 을 비교하여 더 작은 값을 할당하므로 dist[2] = 34
• dist[2] 변경 후 pq에 집어넣음

 

• 우선순위 큐에서 값 빼낸 후 nowVertex에 저장 후 방문 체크
• 정점 1과 인접한 노드는 2, 3번 노드
• dist[2]의 값은 기존의 값이 34와 1번 노드를 거쳐 2번 노드로 가는 경로의 가중치인 8 + 10 = 18을 비교하여 dist[2] = 18로 변경 후 pq에 집어넣음
• dist[3]은 기존의 값인 무한대와 1번 노드를 거쳐 3번 노드로 가는 경로의 가중치인 8 + 5 = 13을 비교하여 dist[3] = 13로 변경 후 pq에 집어넣음

 

• 우선순위 큐에서 값 빼낸 후 nowVertex에 저장 후 방문 체크
• 정점 3과 인접한 노드는 1, 2번 노드
• dist[1]의 값은 기존의 값이 8과 3번 노드를 거쳐 1번 노드로 가는 경로의 가중치인 13 + 1 = 14을 비교하였을 때 기존의 값이 더 작으므로 변경 X
• dist[2]은 기존의 값인 18과 3번 노드를 거쳐 2번 노드로 가는 경로의 가중치인 13 + 13 = 26을 비교하였을 때 기존의 값이 더 작으므로 변경 X

 

• 우선순위 큐에서 값 빼낸 후 nowVertex에 저장 후 방문 체크
• 정점 2과 인접한 노드는 3번 노드
• dist[3]의 값은 기존의 값이 13과 2번 노드를 거쳐 3번 노드로 가는 경로의 가중치인 18 + 2 = 20을 비교하였을 때 기존의 값이 더 작으므로 변경 X

 

• 2번 노드는 방문하였으므로 아무것도 하지 않음

 

최종적으로 dist배열은 위와 같고 각각의 노드들로 가기위한 최소 거리이다.

 

 

 

 

코드 구현

위의 개념과 과정을 토대로 코드의 흐름을 이해한다면 여러 코딩 문제를 풀 때 훨씬 쉽게 응용할 수 있습니다!!

class Node implements Comparable<Node>{
	int index;
	int cost;
	
	public Node(int index, int cost) {
		this.index = index;
		this.cost = cost;
	}

	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.cost, o.cost);
	}
}

public class Main {
	static ArrayList<Node>[] graph;
	
    //노드의 크기, 출발지
	public static void Dijkstra(int n, int start) {
		boolean[] check = new boolean[n + 1];
		int[] dist = new int[n + 1];
		int INF = Integer.MAX_VALUE;
		
		Arrays.fill(dist, INF);
		dist[start] = 0;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start, 0));
		
		while(!pq.isEmpty()) {
			int nowVertex = pq.poll().index;
			
			if(check[nowVertex]) continue;
			check[nowVertex] = true;
			
			//index의 연결된 정점 비교
			for(Node next : graph[nowVertex]) {
				if(dist[next.index] > dist[nowVertex]+ next.cost) {
					dist[next.index] = dist[nowVertex] + next.cost;
					
					pq.offer(new Node(next.index, dist[next.index]));
				}
			}
		}
        
        //최소거리 출력
		for(int i : dist) {
			if(i == INF) System.out.print(0 + " ");
			else System.out.print(i+" ");
		}
	}

	public static void main(String[] args) throws IOException {
    
    //그래프 입력 받기
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		//정점의 개수, 간선의 개수
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());
		
		graph = new ArrayList[n+1];
		for (int i = 0; i <= n; i++)  graph[i] = new ArrayList<>();
		
		StringTokenizer st;
		for(int i = 0 ; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			graph[v].add(new Node(w, cost));
		}

		int start = Integer.parseInt(bf.readLine());

		//다익스트라 알고리즘 수행
		Dijkstra(n, start);
		
	}
}

 

 

 

출처https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘