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

플로이드 와샬 알고리즘이란

• 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘
• 즉, 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶을 때 쓰는 알고리즘
• 다익스트라 알고리즘과 달리 음의 가중치를 가진 간선이 있을 수 있음
• '거쳐가는 정점 기준으로 최단 거리를 구하는 것' (<-> 다익스트라: 가장 적은 비용을 가진 정점 기준)

 

자료구조 및 시간 복잡도

• 모든 정점에 대한 경로를 계산하므로 2차원 배열 사용
• 시간 복잡도: O(n^3) <- 3개의 반복문 

 

알고리즘 구현

for (int k = 0; k < N; ++k) {

    for (int i = 0; i < N; ++i) {

        for (int j = 0; j < N; ++j) {

            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }

        }
    }
}

• 제일 바깥쪽: 거쳐가는 정점
• 두 번째: 출발하는 정점
• 세 번째: 도착하는 정점

 

선행 과정

• 2차원 배열에 두 정점간 비용 초기화 (연결되어있지 않다면 무한대로 초기화)
  • 왜 무한대로 초기화? 무한대를 이용해서 두 정점간의 연결 여부 파악하기 위해

 

 

 

 

 

 

글 작성시 참고:

m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

24. 플로이드 와샬(Floyd Warshall) 알고리즘

mygumi.tistory.com/110

플로이드 와샬 알고리즘 :: 마이구미