◇ 플로이드 워샬 알고리즘
: 모든 노드에서 다른 노드까지의 모든 최단 경로를 계산합니다.
알고리즘은 각 단계를 거치는 노드를 기반으로 실행됩니다.
그러나 Dijkstra와 달리 각 단계에서 방문하지 않은 노드 중에서 가장 짧은 거리를 가진 노드를 찾을 필요는 없습니다.
최단 거리 정보를 2차원 테이블에 저장
DP와의 제휴
시간복잡도가 매우 커서 n의 5제곱>> 에지의 수가 많을 때 Dijkstra를 사용
500개를 초과하는 노드 수는 지정되지 않음
◇ 원칙
각 단계에서 특정 노드 k를 통과하는 경우 확인
: a에서 b까지 k경유 거리가 a에서 b까지의 최단 거리보다 짧은지 확인
재귀 공식 Dab = min(Dab,Dak+Dkb)
◇ 행동과정
0. 그래프 작성 및 최단 거리 테이블 초기화(자체는 0, 엣지가 없으면 INF)
1. 노드 1을 통과하는 경우를 고려하여 테이블 업데이트 Dab = min(Dab, Da1+D1b)
2. 노드 2 ~
>> 모든 노드에서 실행
◇ 의사 코드
# 10억을 무한대로 설정
# 노드 수와 가디언 수 입력 받기
# 2D 목록(그래픽 표현)을 만들고 무한대로 초기화합니다.
# 자체 비용을 0으로 재설정
# 각 edge에 대한 정보를 얻고 이 값으로 초기화
b# A에서 B로 이동하는 비용을 C로 설정
# 재귀 공식에 따라 Floyd-Warshall 알고리즘 실행(3rd for 루프)
# 인쇄 결과
b # 없으면 무한 출력
b # 도달 가능한 경우 인쇄 거리
◇ 실적 분석
노드 수가 N이면 알고리즘은 N 단계를 수행합니다.
O(N^2) 연산으로 현재 노드를 통과하는 모든 경로를 고려합니다.
총 시간 복잡도 O(N^3)