5. Floyd Warshall(플루이드 와샬) : 최단 경로 탐색 - 3

Floyd Warshall (플루이드 와샬)

최단 경로 탐색 - 3

오랜만에 포스팅이다.

주말마다 한 개씩은 쓸라했는데 주말에 좀 바빠서 못썼다...

어제 백준에서 플루이드 와샬 문제를 풀고 갑자기 블로그 포스팅이 생각나서 쓰게 됐다!

 

다익스트라, 벨만 포드에 이은 플루이드 와샬 알고리즘

최단 경로 탐색 카테고리의 마지막 내용이다.

 

다익스트라, 벨만 포드는 특정 노드에서 다른 노드까지의 최단 경로를 탐색해준다.

조금 생각을 바꿔서 모든 노드에서 다른 노드까지의 최단 경로를 탐색하려면 어떻게 해야할까?

 

우선 기존에 배웠던 다익스트라와 벨만 포드를 사용하여 탐색할 수 있다.

다익스트라에서 입력 값으로 넣어주는 src, 즉 출발 노드를 모든 노드로 설정하면 된다.

그만큼 반복문을 돌아야하기에 시간복잡도는 N만큼 증가하게 될 것이다.

 

다익스트라와 벨만 포드를 사용하지 않고도 모든 노드에서 다른 노드까지의 최단 경로를 탐색할 수 있을까?

단순한 중첩 반복문으로 해결할 수 있지 않을까?

 

그렇다. 바로 이것이오늘 설명할 플루이드 와샬 알고리즘이다.

 

단순한 반복문으로 해결할 수 있다고 했는데 어떻게 구현을 해야할까?

개념 자체도 단순하다.

 

정점 i, j, k가 있고 각 정점들 간의 거리가 배열에 저장되어있다고 생각해보자. 아래처럼 말이다.

 

배열 [i][j] -> i에서 j까지의 거리

배열 [i][k] -> i에서 k까지의 거리

배열 [k][j] -> k에서 j까지의 거리

 

그렇다면 아래와 같은 식을 유도할 수 있을 것이다.

 

i에서 j까지 한번에 가는 거리를 배열 [i][j],

i에서 k를 거쳐 j까지 가는 거리를 배열 [i][k] + 배열 [k][j]

 

이제 반복문을 통해

배열 [i][j] > 배열 [i][k] + 배열 [k][j] 인 경우 배열 [i][j] = 배열 [i][k] + 배열 [k][j] 을 해주면 된다!

 

위의 식을 이해했다면 플루이드 와샬 알고리즘을 완벽히 이해한 것이다.

 

위의 개념을 파이썬으로 구현해보았다.

 

 

간단하게 코드를 설명해보자면

거리를 저장할 distance 배열을 INF로 초기화한다.

이후 입력 값을 distance에 넣어주고 src와 dst가 같은 곳은 0으로 바꿔준다.

이후 탐색을 통해 값을 갱신하고 출력한다. (갈 수 없는 정점의 경우 0을 출력한다.)

 

 

[Input]

6 8  # 정점의 개수, 간선의 개수
1 2 6
1 3 4
1 4 4
1 5 2
2 4 5
2 5 7
3 6 10
5 6 2

 

[Output]

 

충남대학교 컴퓨터공학과 이영석 교수님의 알고리즘 수업과 동빈나의 유튜브 강좌(youtu.be/9574GHxCbKc)를 참고했습니다.