• 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다. 즉 정점과 정점, 모든 쌍의 최단 경로를 구하게 된다.
  • 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고  다이나믹 프로그래밍 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.
    • 업데이트 기준 👉 현재 거쳐가는 정점
• 거쳐가는 정점을 기준으로 알고리즘을 수행한다.
  • i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데이트 한다.

소스코드

int INF = 1000000;

int a[4][4] = {
  { 0, 5, INF, 8 },
  { 7, 0, 9, INF },
  { 2, INF, 0, 4 },
  { INF, INF, 3, 0 }
};

// 시간복잡도 V^3
for(int k = 0; k < 4; k++)  // k 는 거쳐가는 정점
  for(int i = 0; i < 4; i++)  // i 는 행 (출발 정점)
    for(int j = 0; j < 4; j++)  // j 는 열 (도착 정점)
      if (a[i][k] + a[k][j] < a[i][j])  // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
        a[i][j] = a[i][k] + a[k][j];

추가)

간선이 하나씩만 연결 되어 있더라도 모든 최소값을 다 구할 수 있다.

다이나믹을 활용하기 때문이다.

Reference

• https://blog.naver.com/ndb796/221234427842
• https://ansohxxn.github.io/algorithm/floyd/
• 관련 문제
  • 백준 1058번 : 친구
  • 백준 5567번 : 결혼식
  • 백준 10159번 : 저울 (플로이드 와샬 응용)
  • 프로그래머스 : 배달
  • 백준 1238 : 파티