Floyd-Warshall

플루이드-워셜: 그래프에서 최단거리를 구하는 알고리즘

• 기능: 모든 노드 간에 최단 경로 탐색

• 특징

  • 음수 가중치 edge가 있어도 수행 가능(음수 cycle은 있어서 안됨)
  • 동적 계획법의 원리를 이용해 알고리즘에 접근

• 시간 복잡도: O(V^3) ( 노드 수의 세제곱)

• floyd-warshall 핵심 이론

  

  • A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.
  • 1→5 최단 경로가 초록색 간선이라면 1→4경로와 4→5 경로 역시 색칠 된 간선으로 이뤄질 수 밖에 없다.
  • 즉, 전체의 최단 경로는 각 부분 경로를 합한 것이라고 볼 수 있다.

• 플루이드-워셜 점화식

  • D[S][E] = min( D[S][E], D[S][K] + D[K][E])
  • K노드는 S,E 사이에 있는 모든 노드

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

   

   1. 주 대각선은 0으로 초기화. 자신한테 가는 시간은 0이므로 자기 자신한테 가는 데 걸리는 최단경로값 0
   2. 다른 칸은 무한대로 초기화

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

   

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

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

      

   2. ****제일 바깥쪽 for문이 K이다.****

   3. 나머지 for문은 start와 end노드이다.

   4. 3중 for문을 돌리면 바로 최단 경로가 나온다.