[알고리즘] 플로이드-워셜(floyd-warshall)

1. 플로이드 워셜이란

그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘이다.

 

2. 특징

• 음수 가중치 에지가 있어도 알고리즘 수행이 가능하다.
• 동적 계획법의 원리를 이용하여 알고리즘에 접근한다.
• 그래프를 인접 행렬로 표현한다.

 

3. 핵심 원리

A노드에서 B노드까지 최단 경로를 구했을 때, 최단 경로 위에 K노드가 존재한다고 하면, 그것을 이루는 부분 경로 역시 최단 경로다.

• '최단 경로 위에 K노드가 존재한다고 하면, 그것을 이루는 부분 경로 역시 최단 경로다.'라는 말이 무슨 뜻이냐면
• 위와 같은 그래프가 있을 때, 노드1에서 노드 5로 가는 최단 거리는 1 -> 2 -> 4 -> 5로 가는 경로가 최단 경로이다.
• 이러한 결과를 얻었을 때, 1 -> 2, 2 -> 4, 혹은 1 -> 4로 가는 경로 또한 최단 경로가 된다는 뜻이다.

 

4. 알고리즘 로직

1. 배열 선언 및 초기화

• S == startNode, E == endNode
• 그렇다면 D[S][E] S에서 E까지의 거리를 뜻한다.
• 배열을 초기화 할 때는 S == E 인 경우, 자기 자신이므로 0으로 나머지 경우는 무한대로 초기화한다.

2. 그래프 데이터 최단 거리 배열에 저장

• 최단 거리 배열에는 W(가중치)를 저장한다.
• 위의 그래프를 예로 들면 D[1][2] = 8, D[1][3] = 3이 되겠다.

S\E	1	2	3	4	5
1	0	8	3	99,999,999	99,999,999
2	99,999,999	0	99,999,999	-4	15
3	99,999,999	99,999,999	0	13	99,999,999
4	99,999,999	99,999,999	99,999,999	0	2
5	99,999,999	99,999,999	99,999,999	5	0

3. 점화식으로 배열 업데이트

점화식 : 
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

• 3중 for문으로 점화식을 사용하여 배열을 업데이트한다.

// S : 출발노드, E : 도착노드, K : 경유지, N : 노드 개수
for( K에 대해서 1 ~ N번)
	for( S에 대해서 1 ~ N번)
    	for( E에 대해서 1 ~ N번)

 

3. 시간 복잡도 : O(V^3)

 

4. 플로이드 워셜 문제 풀어보기