[알고리즘]플로이드 와샬(Floyd-Warshall) 알고리즘

suhyun·2022년 11월 26일
0

알고리즘 정리

목록 보기
2/5
post-thumbnail

플로이드-와샬 알고리즘

모든 최단 경로를 구하는 알고리즘

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이지만,
플로이드-와샬 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있음

하지만 시간복잡도가 O(n^3)이기 때문에, 그래프의 크기가 작아 세제곱 시간을 알고리즘에 적용해도 문제가 풀릴때만 사용할 수 있음!

알고리즘 진행 과정

모든 노드 간의 최단 거리를 구하기 위해서 2차원 인접 행렬 이용
인접 행렬은 한번에 구성되는것이 아니라 과정을 단계적으로 진행하며 최단 경로를 선택해 수정한다.


초기 그래프를 인접 행렬로 나타내면 아래와 같다.
INF는 해당 노드에서 특정 노드까지의 경로가 존재하지 않는 경우이다.


① 노드1을 지나쳐가는 경우

색칠한 부분만 갱신해주면 되는데 이때 비교식이 필요하다.

A에서 B로 가는 최소 거리A에서 1로 가는 거리 + 1에서 B로 가는 거리 를 비교하는 것이다.
즉, 노드1을 거쳐가는 경우가 더 빠른 경우라면 값을 갱신해주면 된다.


② 노드2를 지나쳐가는 경우


③ 노드3을 지나쳐가는 경우


④ 노드4를 지나쳐가는 경우

결과적으로 위와 같은 행렬이 만들어진다.

소스 코드 (java)

최단 거리 행렬 초기화

가지고 있는 인접 행렬을 통해서 최단거리 행렬을 초기화한다.

자기 자신으로 가는 경로의 경우에는 0
경로가 존재하지 않는 경우에는 INF
존재하는 경우에는 인접 행렬의 값을 입력한다.

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

for문을 통한 행렬 갱신

이때 중간 노드가 될 노드를 가장 바깥 for문의 변수로 설정한다.
i와 j를 통해 모든 노드를 확인하며 k를 중간 노드로 설정할 때와 아닐때의 값을 비교해 최단 거리로 갱신한다.

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}
profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글