[Algorithm] Floyd-warshall algorithm

플로이드-와샬 알고리즘

플로이드 알고리즘이란

• 모든 최단 경로를 구하는 알고리즘이다.

  • 즉 모든 정점에서 모든 정점까지의 최단 거리를 구할 수 있다.
  • 다이나믹 프로그래밍 방식으로 최단거리를 업데이트 한다.

• 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다.

  • i에서 j로 가는 경우와 i에서 k를 거쳐 j로 가는 경우 중 더 짧은것으로 업데이트한다.

플로이드 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다.

코드

void Floyd() // 플로이드-와샬 알고리즘
{
  // i :거쳐가는 정점
	for (int i = 1; i <= vertex; i++)
	{
    // j: 행 (출발 정점)
		for (int j = 1; j <= vertex; j++)
		{
      // k: 열 (도착 정점)
			for (int k = 1; k <= vertex; k++)
			{
					matrix[j][k] = min(matrix[j][k], matrix[j][i] +matrix[i][k]);
				}
			}
		}
	}
}

• j에서 k로 가는 경우
  • min함수를 통해 j에서 k와 j에서 i를 거쳐 k를 비교한다.
  • 더 짧은 거리를 matrix[j][k]의 거리로 업데이트한다.

반복을 통해 모든 정점끼리의 최단거리를 구할 수 있다.

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기

첫 번째 글입니다 가장 최근 글입니다