플로이드-워셜 솔루션

[1. 개요]

일관 된 구현 패턴을 유지하도록 한다.

• 경유지 (k)
• 출발지 (u)
• 목적지 (v)

덧셈 간 자료형 내 오버플로우가 발생하지 않는 값을 MAX weight 로 설정하도록 한다.

 

경로 복원

• u -> v 에서 경유지 k 가 사용 된 경우 이를 별도 배열에 저장한다.
  path[u][v] = k
• 이 후, 재귀 함수를 이용하여 u ~~~ v 경로를 구하도록 한다.
  => u ~~~ v
  => u ~~~ k ~~~ v
  => u ~ k 에 대한 부분 문제를 해결
  => k ~ v 에 대한 부분 문제를 해결
  => ... 

 

 

[2. 예제]

• https://testkernelv2.tistory.com/491
• b
• c
• d
• e
• g