플로이드-워셜

그래프 내의 모든 쌍 최단 경로 문제를 해결하는 데 사용되는 알고리즘이다. 주어진 그래프에서 모든 정점 쌍 사이의 최단 경로 거리를 계산하며, 그래프는 가중치가 있는 방향 그래프일 수 있다. 동적 계획법을 사용하여 점진적으로 최단 경로를 찾는다.

🔍 단계

1. 초기화: 그래프의 인접 행렬을 초기화한다.
   dist[i][j]는 i에서 j로 가는 경로의 가중치로 초기화된다.
   만약 i에서 j로 직접 경로가 없다면 무한대로 초기화한다. dist[i][i]는 0으로 설정한다.
2. 갱신: 세 개의 중첩된 루프를 통해 모든 쌍에 대해 최단 경로를 갱신한다.
   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

🔍 순서

다음과 같은 세 가지 중첩된 루프를 사용한다.

1. 중간 노드 k를 선택한다.
2. 시작 노드 i를 선택한다.
3. 도착 노드 j를 선택한다.

이 중첩 루프는 모든 i와 j에 대해 경로 i -> k -> j가 기존 경로 i -> j보다 짧은지 확인하여 최단 경로를 업데이트한다.

예제 코드의 그래프는 인접 행렬로 표현되며, graph[i][j]는 노드 i에서 노드 j로 가는 간선의 가중치를 나타낸다.
sys.maxsize는 무한대를 나타내며, 경로가 없음을 의미한다. 알고리즘이 수행된 후, dist[i][j]는 노드 i에서 노드 j로 가는 최단 경로의 가중치를 포함한다.

import sys

def floyd_warshall(graph):
    # 정점의 수
    V = len(graph)
    
    # 최단 거리 행렬 초기화
    dist = [[sys.maxsize] * V for _ in range(V)]
    
    # 그래프 초기화
    for i in range(V):
        for j in range(V):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # Floyd-Warshall 알고리즘 적용
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# 예제 그래프
graph = [
    [0, 3, sys.maxsize, 7],
    [8, 0, 2, sys.maxsize],
    [5, sys.maxsize, 0, 1],
    [2, sys.maxsize, sys.maxsize, 0]
]

# 최단 거리 계산
dist = floyd_warshall(graph)

# 최단 거리 행렬 출력
print("최단 거리 행렬:")
for row in dist:
    print(row)

✅ 플로이드 워셜과 동적 계획법 비교

구분	플로이드-워셜 알고리즘	동적 계획법
적용 문제	모든 쌍 최단 경로 문제 (그래프)	다양한 최적화 문제 (피보나치, 배낭 문제 등)
구조	특정 문제 해결을 위한 알고리즘	일반적인 문제 해결 방법론
시간 복잡도	O(V^3) (정점의 개수가 V인 그래프에 대해)	문제에 따라 다름 (예: 피보나치 수열 - O(n), 배낭 문제 - O(nW))
알고리즘 방식	3중 루프를 사용하여 모든 정점 쌍을 탐색	재귀적(탑다운) 또는 반복적(바텀업) 접근 가능
구체적 목표	그래프 내 모든 정점 쌍 사이의 최단 경로를 찾음	다양한 문제에 대해 최적해 또는 근사해를 찾음

💻 빈출 예제

1. 모든 쌍 최단 경로 문제
그래프가 주어졌을 때, 모든 정점 쌍 사이의 최단 경로를 구하는 문제.

2. 그래프 내에서 특정 경로의 존재 여부 확인
특정 정점 쌍 사이에 경로가 존재하는지 확인하는 문제.
플로이드-워셜 알고리즘을 사용하면 모든 쌍의 최단 경로 정보를 알 수 있으므로, 이를 통해 경로의 존재 여부를 쉽게 확인할 수 있다.

3. 최단 경로를 통한 경유지 결정
두 정점 사이를 이동할 때 특정 정점을 반드시 경유해야 하는 경우의 최단 경로를 찾는 문제.

4. 그래프에서의 최단 경로의 최대 비용 찾기
그래프의 모든 쌍 최단 경로 중에서 가장 긴 경로(최대 비용)를 찾는 문제.
플로이드-워셜 알고리즘을 사용하여 모든 쌍의 최단 경로를 계산한 후, 이들 중에서 최대 값을 찾으면 해결된다.

5. 네트워크 지연 시간 계산
네트워크에서 패킷이 전달되는 시간을 계산하는 문제.
모든 노드 쌍 사이의 지연 시간을 구하고, 이를 기반으로 네트워크 성능을 분석할 수 있다.

6. 도로 네트워크 분석
도로 네트워크에서 각 도시 쌍 간의 최단 경로를 계산하는 문제.
도시 간 이동 시간을 최적화하는 데 사용될 수 있다.

7. 경로 복원
두 정점 사이의 최단 경로를 실제로 복원하는 문제.
플로이드-워셜 알고리즘의 중간 정점 정보를 사용하여 경로를 추적할 수 있다.