2021년 09월 17일 TIL - 플로이드 와샬 알고리즘 (Java)

문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다.

(대충 3중 for문 이라는 것 정도..)

특징

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘.

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘.

3중 for 문

• (제일 밖) 첫 번째 for 문: 거쳐가는 노드
• 두 번째 for 문 : 출발 노드
• 세 번째 for 문 : 도착 노드

검증

• 출발→거쳐 + 거쳐→도착 가 출발→도착 보다 더 짧으면? 출발→도착 갱신.

Code

for(int k = 0; k < number ; k++) {
    for(int i = 0; i < number ; i++) {
        for(int j = 0; j < number ; j++) {
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];
        }
    }
}