[알고리즘] 다익스트라

다익스트라 알고리즘

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

- 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 기록

- 해당 정점까지의 최단 거리 저장 & 정점을 방문했는지 저장

 

알고리즘 순서

1. 최단 거리 값 = 무한대 값으로 초기화

for(int i = 1; i <= n; i++){
    distance[i] = Integer.MAX_VALUE;
}

2. 시작 정점의 최단 거리 = 0 & 시장 정점 방문 처리

distance[start] = 0;
visited[start] = true;

3. 시작 정점과 연결된 정점들의 최단 거리 값 갱신

for(int i = 1; i <= n; i++){
    if(!visited[i] && map[start][i] != 0) {
    	distance[i] = map[start][i];
    }
}

4. 방문하지 않은 정점 중 최단 거리가 최소인 정점 찾기

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;
        }
    }
}

5. 찾은 정점에 방문 체크 후 , 해당 정점과 연결된 방문하지 않은 정점의 최단거리 값 갱신

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];
        }
    }
}

6. 모든 정점 방문할 때까지 4~5번 반복