[python] 플로이드-와샬 알고리즘

최단 경로 알고리즘

• 그래프에서 노드 간의 최소 비용 경로를 찾는 알고리즘.
• 주로 길 찾기 문제에 적용되며, 그래프의 각 지점을 노드로, 지점 간 연결된 도로를 간선으로 표현.

대표 알고리즘

• 다익스트라
• 벨만-포드
• 플로이드와샬

플로이드-와샬

• 플로이드 와샬 알고리즘은 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 동적 계획법 기반 알고리즘입니다.

주요 특징

• 모든 정점 간 최단 경로 계산
• 음수 가중치 간선 처리 가능
• 시간 복잡도 O(N³)
• 음수 사이클이 없는 그래프에서 사용

동작 원리

• 모든 노드 간 직접 연결된 간선으로 초기 거리 행렬 생성
• 각 노드를 중간 경유지로 고려
• 중간 노드를 거쳐가는 경로가 더 짧으면 최단 거리 갱신
• 모든 노드에 대해 반복

코드

def floyd_warshall(graph):
    # 노드 수
    n = len(graph)

    # 최단 거리 테이블 초기화
    dist = [[float('inf')] * n for _ in range(n)]

    # 그래프 초기화
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0  # 자기 자신으로 가는 경로는 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]  # 간선이 존재하면 가중치로 초기화

    # 플로이드 와샬 알고리즘 수행
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 중간 노드 k를 거쳐가는 경로가 더 짧으면 갱신
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# 예제 그래프 (인접 행렬)
graph = [
    [0, 3, float('inf'), 7],
    [8, 0, 2, float('inf')],
    [5, float('inf'), 0, 1],
    [2, float('inf'), float('inf'), 0]
]

# 알고리즘 실행
result = floyd_warshall(graph)
for row in result:
    print(row)