플로이드 워셜

2025.04.03 - [분류 전체보기] - 다익스트라

다익스트라

한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이었던 다익스트라 알고리즘이 있지만,
더 무식하게 모든 경우를 구해야하는 상황도 있다. 그런 상황에 있어 적합한 해결책으로 제시 되는 것은 플로이드 워셜 알고리즘이다.

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용

dist[i][j]는 정점 i에서 정점 j까지의 현재 최단 거리. k는 경유지로 사용할 중간 정점을 말한다.

최단 경로라는 개념을 언급하는 시점에서 알 수 있는 것은 이번에도 가중치가 있는 방향 그래프에서 사용 된다고 암시된다.

이 알고리즘은 동적 프로그래밍을 기반으로 작동한다.
특정 경로를 통해 다른 경로로 이동했을 때 짧아지는 경우를 반복적으로 계산하여 최적의 경로를 구하게 된다.

동작 과정

• 초기화
  • dist[i][j]는 i에서 j로 직접 연결된 간선의 가중치로 설정한다.
  • 연결되지 않은 경우는 무한대로 설정한다.
  • 자기 자신으로 가는 경로 dist[i][i]는 0으로 초기화한다.
• 경유지 고려
  • 모든 정점을 경유지로 삼아, 두 정점 사이의 최단 거리를 업데이트한다.
• 결과
  • 최종적으로 모든 정점 쌍 사이의 최단 거리가 dist 행렬에 저장된다.

시간 복잡도

• O(V^3) : V는 그래프의 정점 갯수를 말한다.
  • 중첩된 3개의 반복문 때문에 정점 갯수에 따라 성능이 급격히 저하된다.
  • 플로이드 워셜 알고리즘은 정점 수가 작거나 간선 수가 많은 밀집 그래프에 제일 적합하다.

장점과 단점

• 장점
  • 간단하고 명확하게 구현된다.
  • 모든 쌍의 최단 경로를 한 번에 계산 할 수 있다.
  • 음수 가중치를 가진 간선에서도 작동.
• 단점
  • 앞에서 본 시간 복잡도를 생각해보면, 대규모 그래프에서는 비효율적이다.
  • 음수 사이클이 존재하는 경우 사용 불가능하다.

def floyd_warshall(graph):
    V = len(graph)
    dist = [[float('inf')] * V for _ in range(V)]

    # 초기화
    for i in range(V):
        for j in range(V):
            dist[i][j] = graph[i][j]

    # 경유지 k를 통해 i에서 j로의 최단 거리 계산
    for k in range(V):
        for i in range(V):
            for j in range(V):
                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)