floyd warshall

플로이드 워셜

시간 복잡도 : O(V^3) (V : 정점의 개수)

V가 크면 사용하지 못함에 주의하자

특징

• 단 방향 그래프
• 어떤 특정 정점을 거쳤을 때의 경로가 최단이라면 table을 update한다.
• 이전에 구했던 최단 경로를 통해 새로운 최단 경로를 찾는 방식으로 진행된다.

참고

자료구조

연결 관계를 나타내는 그래프를 만들어야한다.

V가 크지 않으므로 vector가 아닌 2차원 배열로 관리함에 유의하자.

연결 관계 배열은 MAX 값으로 초기화한다.

// costs[from][to]
int costs[MAX_SIZE][MAX_SIZE];

// initialize
for (int i = 1; i <= N; i++) {
  for (int j = 1; j <= N; j++) {
    costs[i][j] = i == j ? 0 : MAX;
  }
}

void floyd_warshall() {
  for (int through = 1; through <= N; through++) {
    for (int from = 1; from <= N; from++) {
      for (int to = 1; to <= N; to++) {
        costs[from][to] = min(costs[from][to], costs[from][through] + costs[through][to]);
      }
    }
  }
  return;
}