[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

 

1. 개념

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점' 까지의 최단경로를 모두 구해야 하는 경우에 사용한다. '한 지점' 에서 나머지 지점의 최단경로를 구하는 다익스트라 알고리즘과는 용도가 사뭇 다르다.

다익스트라보다 소스 코드는 간결한 편이지만, 알고리즘 컨셉을 이해하는 것이 중요하다.

다익스트라 알고리즘에 대한 개념은 아래 글에 정리해두었다.

 

codingexplore.tistory.com/51

[ 알고리즘 개념 ] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

 

※ 다익스트라 알고리즘 vs 플로이드 워셜 알고리즘

 

	다익스트라 알고리즘 (Dijkstra Algorithm)	플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)
개념	한 지점에서 나머지 지점의 최단경로	모든 지점에서 다른 모든 지점의 최단경로
동작	단계마다 최단거리를 가지는 노드를 반복 선택하며 최단 거리 테이블 갱신	단계마다 '거쳐 가는 노드' 를 기준으로 현재 노드를 거쳐가는 '모든 경로' 고려 O(V^2) - 이 과정을 V단계 수행
최단거리 저장 자료형	1차원 리스트	2차원 리스트
방법론	그리디 알고리즘	다이나믹 프로그래밍
시간복잡도	O(ElogV)	O(V^3)

 

2. 동작 과정

다익스트라 알고리즘과는 달리 플로이드 워셜 알고리즘은 매 단계마다 방문하지 않은 노드 중에서 최단 거리인 노드를 찾지 않는다. 대신에 현재 노드를 거쳐가는 모든 경로를 고려 해야 한다.

 

( 노드의 개수가 V개일 때)

 

1) 최단 거리 테이블 (2차원 리스트) 초기화

 

2) 현재 노드를 거쳐가는 모든 경로를 확인 - O(V^2) : 2차원 리스트 갱신 비용

- 만약 A 에서 B로 가는 비용이 3이라고 저장되어 있을 때,

- 현재 노드가 3번노드이고 A -> 3번노드 -> B 경로가 비용이 1이면 (즉, 최단거리 테이블에 저장된 값보다 작으면)

- 최단거리 테이블을 갱신한다.

 

3) 2번 과정을 모든 노드에 걸쳐 시행한다. - V 회 반복

 

2차원 리스트를 갱신 ( O(V^2) ) 하는 과정을 -> 모든 노드에 걸쳐 V회 시행 -> 3중 for문 사용

∴ 시간복잡도 O(V^3)

 

3. 동작 예

 

플로이드 워셜 그래프 예

 

＃S0 : 최단거리 테이블 초기화 - 아직 노드 선택하기 전이므로 직접 연결된 경로만 테이블에 저장

 

---

 

＃S1 : 1번 노드 - 1번 노드를 거치는 경로 검토

: 3번노드 -> 2번노드 경로 갱신 ( INF -> 12 )

: 3번노드 -> 4번노드 경로 갱신 ( INF -> 5 )

---

＃S2 : 2번 노드 - 2번 노드를 거치는 경로 검토

: 4번노드 -> 3번노드 경로 갱신 ( 9 -> 3 )

: 1번노드 -> 3번노드 경로 갱신 ( INF -> 9 )

---

＃S3 : 3번 노드 - 3번 노드를 거치는 경로 검토

: 2번노드 -> 1번노드 경로 갱신 ( INF -> 5 )

: 2번노드 -> 4번노드 경로 갱신 ( INF -> 6 )

---

＃S4 : 4번 노드 - 4번 노드를 거치는 경로 검토

: 1번노드 -> 2번노드 경로 갱신 ( 8 -> 3)

: 3번노드 -> 2번노드 경로 갱신 ( 12 -> 7 )

 

 

관련글

다음은 플로이드 워셜 알고리즘을 어떻게 구현할 것인지에 대한 것을 다뤄보고자 한다.

아래 게시글에 정리해두었다.

codingexplore.tistory.com/54

[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python)

---

참고자료

www.semanticscholar.org/paper/All-Pairs-Shortest-Paths-and-the-Floyd-Warshall-Mount/9cb9e82f482d434cf73ec2dd747662e0dc741caf/figure/1

Figure 2 from All-Pairs Shortest Paths and the Floyd-Warshall Algorithm | Semantic Scholar

www.gatevidyalay.com/floyd-warshall-algorithm-shortest-path-algorithm/

Floyd Warshall Algorithm | Example | Time Complexity | Gate Vidyalay