플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 정점 쌍의 최단 경로를 구하는 알고리즘으로, 음수 가중치가 있는 경우에도 사용할 수 있으나 음수 사이클이 있으면 올바른 결과를 보장하지 않습니다.

주요 특징

• 동적 계획법(Dynamic Programming) 사용:
  • 각 정점 쌍의 최단 거리를 점화식에 따라 갱신합니다.
• 모든 정점 쌍 최단 경로:
  • 그래프의 모든 정점에서 정점으로의 최단 경로 비용을 구합니다.
• 음수 가중치 처리 가능:
  • 음수 가중치가 있는 간선도 처리할 수 있으나, 음수 사이클이 존재하면 문제가 발생합니다.

알고리즘 개념

• dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
• 초기화:
  • 각 정점 쌍에 대해, 직접 연결되어 있다면 해당 가중치로 초기화하고, 연결되어 있지 않다면 무한대(∞)로 초기화합니다.
  • 자기 자신으로의 경로는 0으로 설정합니다.
• 점화식:
  • 모든 정점을 중간 정점으로 고려하여 아래의 점화식을 반복 적용합니다.
• 여기서 dist[i][j]는 정점에서 정점으로 가는 현재까지의 최단 거리를 의미합니다.

알고리즘 동작 방식

1. 초기화 단계:
   • 모든 정점 쌍의 최단 거리 배열 dist를 설정합니다.
   • 직접 연결된 정점은 간선의 가중치로, 연결되지 않은 정점은 무한대로 초기화합니다.
   • 자기 자신에 대한 거리는 0으로 설정합니다.
2. 갱신 단계:
   • 모든 정점을 중간 정점으로 하여, 모든 정점 쌍에 대해 최단 거리를 갱신합니다.

응용 분야 및 주의 사항

• 응용 분야:
  • 네트워크 최적화, 지도 서비스, 교통 네트워크 분석 등
  • 최단 경로 복원 문제: 별도의 배열을 사용하여 실제 경로를 추적할 수 있음
• 주의 사항:
  • 음수 사이클이 존재하면 최단 경로 계산이 의미 없으므로, 사전에 음수 사이클 검사가 필요함
  • 정점의 수가 매우 많을 경우 메모리 사용량과 시간 복잡도에 주의해야 함

관련 문제 (백준)

11403 (경로 찾기)

11404 (플로이드)