Intro::
다익스트라 알고리즘에 대해 알아보자.
정의
DP를 활용한 최단 경로 알고리즘이다.
여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다.
다익스트라를 구현하기 위해 필요한 인자들
- 해당 정점까지의 최단 거리를 저장
- 정점을 방문했는 지 저장
코드
- 최단 거리 값은 무한대 값으로 초기화한다.
for(int i = 1; i <= n; i++){ distance[i] = Integer.MAX_VALUE; }
- 시작 정점의 최단 거리는 0이다. 그리고 시작 정점을 방문 처리한다.
distance[start] = 0; visited[start] = true;
- 시작 정점과 연결된 정점들의 최단 거리 값을 갱신한다.
for(int i = 1; i <= n; i++){ if(!visited[i] && map[start][i] != 0) { distance[i] = map[start][i]; } }
- 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는다.
int min = Integer.MAX_VALUE; int midx = -1; for(int i = 1; i <= n; i++){ if(!visited[i] && distance[i] != Integer.MAX_VALUE) { if(distance[i] < min) { min = distance[i]; midx = i; } } }
- 찾은 정점을 방문 체크로 변경 후, 해당 정점과 연결된 방문하지 않은 정점의 최단 거리 값을 갱신한다.
visited[midx] = true; for(int i = 1; i <= n; i++){ if(!visited[i] && map[midx][i] != 0) { if(distance[i] > distance[midx] + map[midx][i]) { distance[i] = distance[midx] + map[midx][i]; } } }
- 모든 정점을 방문할 때까지 4~5번을 반복한다.
Loading Comments...