Written by nodejs-style
on 2021-12-22

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

Abstract

DP를 활용한 최단경로탐색 알고리즘

알고리즘 하나의 최단 거리를 구할 때 그 이전 까지 구했던 최단거리 정보를 그대로 사용

Process

출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택 선정된 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 3,4 단계를 반복

Java Code

DP를 활용한 다익스트라

private int min(int a, int b){ if (a 아직 방문하지 않음, true -> 이미 방문 for(int i = 0; i < N; i++){ // dist, visited 배열 초기화 dist[i] = graph[0][i]; visited[i] = false; } visited[0] = true; for(int i = 0; i < N-2; i++){ // N-2개의 마을을 방문하는 동안 반복(1번과 마지막 마을 제외) int min = INF; int idx = 0; // 1번 마을에서 방문하지 않은 마을 중 가장 비용이 적은 마을 번호를 탐색 for(int j = 1; j < N; j++){ if(dist[j] < min && !visited[j]){ min = dist[j]; idx = j; } } visited[idx] = true; // i번 노드에서 선정된 노드(idx)를 거쳐서 특정한 노드(j)로 가는 경우를 고려하여 최소 비용을 갱신 for(int j = 1; j < N; j++){ if(dist[j] > dist[idx] + graph[idx][j]){ dist[j] = dist[idx] + graph[idx][j]; } } } for(int D : dist){ if(D <= K) answer++; } return answer; }

우선순위 큐를 활용한 다익스트라

추가예정