플로이드 워셜 알고리즘

1. 개념

플로이드 워셜 알고리즘은 다익스트라와 같이 최단 경로 알고리즘 중의 하나로,

가중치가 있는 그래프에서 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다.

 

다익스트라 같은 경우는 단일 노드에서 다른 모든 노드까지의 최단 경로였지만 여기서는 모든 노드 쌍 간의 최단 경로이다..!

 

아래에서 구현 코드와 함께 이해해보자.

 

 

---

2. 코드 이해

플로이드 알고리즘의 코드 구조를 매우 간단하다.

 

일단 모든 노드 쌍 간의 최단거리를 구해야 하므로 n^2의 계산이 필요하다.

여기에서는 i → j 까지 직행으로 가는 거리를 구할 수 있다.

for i in range(n):    	# 출발지
    for j in range(n):	# 도착지
        dist[i][j]

 

 

위 수식에서 i → j 까지 갈 때, 경유지를 고려하면 플로이드 알고리즘이 완성된다.

i → j 까지 직행 거리와 i → k → j 로 경유지를 들린 거리를 비교해 최단 거리를 갱신해나가면 된다.

 

그러면 k는 가장 바깥의 for 문으로 정의하여, 경유 가능한 노드를 늘려가며 된다. 

• k = 0 일 때는, 0번 노드 경유지 허용
• k = 1 일 때는, 1번 노드 경유지 허용
• k = 2 일 때는, 1·2번 노드 경유지 허용

for k in range(n):        	# 경유지
    for i in range(n):    	# 출발지
        for j in range(n):	# 도착지
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

 

---

3. 문제

지금까지 풀었던 플로이드 알고리즘 유형에 대한 문제 풀이 리스트이다.

 

 

* BOJ - 11265. 끝나지 않는 파티 (골드 4)

• https://wch-0625.tistory.com/72

 

* BOJ - 14938. 서강그라운드 (골드 4)

• https://wch-0625.tistory.com/73

 

* BOJ - 1719. 택배 (골드 3)

• https://wch-0625.tistory.com/84

 

* BOJ - 11562. 백양로 브레이크 (골드 3)

• https://wch-0625.tistory.com/104