알고리즘 코딩테스트 핵심이론 강의 - 플로이드-워셜

https://www.youtube.com/watch?v=ibYzw9XAzyc&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=33

📌 플로이드 - 워셜

• 그래프에서 최단 거리를 구하는 알고리즘
• N의 크기가 크면 프로이드-워셜을 사용하지 않는것이 좋다. (시간 복잡도)
  노드 100개 ~ 200개 사이가 적당

기능특징시간 복잡도(노드수 : V , 에지 수 : E)

모든 노드 간 최단 경로 탐색

- 음수 가중치 에지가 있어도 수행 가능 - 동적 계획법 원리를 이용해 알고리즘에 접근

O(V³)

 

◾ 플로이드 - 워셜 원리

• A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로
  → 색칠 된 경로가 1에서 5까지 최단 경로라면 1 → 4 최단 경로와 4 → 5 최단 경로 역시 색칠 된 에지로 이루어 질 수밖에 없다.

🔶 도출한 플로이드-워셜 점화식

D[S][E] = Math.min( D[S][E], D[S][K] + D[K][E] )

1. 리스트를 선언하고 초기화 하기

• D[S][E]는 노드 S에서 노드 E까지의 최단거리를 저장하는 리스트라 정의
  S와 E의 값이 같은 칸은 0 , 다른 칸은 ∞로 초기화
  여기서 S==E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미
  내 자신에게 가는 시간은 0이기 때문에

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

• 출발 노드는 S, 도착 노드는 E, 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 리스트에 입력
  이로써 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있음

 

 

3. 점화식으로 리스트 업데이트 하기

• 기존에 구했던 점화식을 3중 for문 형태로 반복하면서 리스트 값을 업데이트

🔶 플로이드-워셜 알고리즘 로직

• 가장 바깥쪽이 K, S, E 순서이다.

for ( int K=0; K<N; K++) {
	for ( int S=0; S<N; S++){
		for ( int E=0; E<N; E++){   
        	D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
            // 기존 값 (D[S][E]) 보다 특정 수 (K)를 거쳐서 가는 수 (D[S][K] + D[K][E])가 작으면
            // 기존 값을 작은 수(D[S][K] + D[K][E])로 업데이트
    	}
    }
}

• 완성된 리스트는 모든 노드간의 최단거리를 알려준다.
  예를들어 1번 노드에서 5번 노드까지 가는 최단 거리는 D[1][5] = 6으로 나타나는 것을 알 수 있음
• 모든 노드 간의 최단 거리를 확인 해 주기 때문에 시간 복잡도가 빠르지 않은 편
• 노드 개수의 범위가 다른 그래프에 비해 적게 나타남