[최단거리] 플로이드 와샬 알고리즘

☝🏻 양수 , 음수 가중치가 존재하는 최단 거리

☝🏻 전체 쌍 : 그래프 내 모든 노드 쌍 사이의 최단 경로

☝🏻 작은 그래프에 적합 : 플로이드 워샬 알고리즘은 시간 복잡도 O(V^3)가 높기 때문에, 노드 수가 많지 않은 문제에 적합 (V=100개 이하에서 가장 proper!)

☝🏻 음의 사이클 처리 : 음의 사이클이 존재하면 제대로 동작하지 않기 때문에, 음의 사이클이 없는지 확인하는 것이 중요하다.

플로이드 와샬 특징

• 용도: 모든 쌍의 최단 경로를 찾는 알고리즘
• 그래프 유형: 음의 가중치를 허용하지만, 음의 사이클이 없는 그래프
• 장점: 구현이 간단하고, 모든 쌍의 최단 경로를 구할 수 있음
  • DP를 사용해서 구현한다.
• 단점: 시간 복잡도가 높아 큰 그래프에서는 비효율적

알고리즘

시간 복잡도 O(V^3)

• dp를 사용해서 그래프의 모든 정점 쌍 사이의 최단 경로를 구한다. 3중 루프를 통해서 모든 가능한 경로를 검사하고, 최단 경로를 업데이트 하는 방식으로 작동한다.
• dp를 사용한다구요 ?
  • 플로이드 워샬은 “거쳐가는 정점”을 이용해서 최단 경로를 점진적으로 개선하는 방법이다.
  • i에서 j로 가는 최단 거리가 정점 k를 거쳐가는 경우 더 짧아질 수 있다면, 그 값으로 최단 거리를 갱신하는 방식이다.

1. 최단거리 배열 초기화 - 플로이드 워샬을 사용하기 위한 세팅

• 2차원 배열을 사용해서 최단거리 배열 dist를 만든다.
• dist[i][j] 는 i에서 j로 가는 최단 거리를 의미한다.
• dist를 int(1e9)으로 초기화 할 것인데,
• 자기 자신으로 가는 거리는 0으로 초기화
• 직접 연결된 간선은 해당 가중치로 초기화

for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        else:
            dist[i][j] = graph[i][j] if (i, j) in graph else float('inf')

2. 점진적 개선 - 플로이드 워샬의 꽃

• i부터 j까지 가는데 모든 가능한 k를 들리는 경우를 고려하려고 한다 !!! 정점 k를 거쳐가는 경로가 기존의 경로보다 더 짧은지 확인하고, 짧으면 갱신하는 방식이다. (=경로 i -> j를 경로 i -> k -> j와 비교하여 더 짧은 경로를 찾으면 갱신)
• : 플로이드 워샬의 핵심은 i에서 j까지 가는데 k를 들리면 더 최단 거리가 발생할 수 있다는 것이니까 !!
• 3개의 중첩 for문을 사용해서 모든 쌍 (i, j)에 대해 모든 중간 정점 k를 고려한다.
• dist[i][j]는 dist[i][k] + dist[k][j]보다 크면, dist[i][j]를 갱신한다.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

3. 음의 사이클 감지

• 플로이드 와샬은 음의 가중치일 때 사용 가능하지만, 음의 사이클이 있으면 안된다. 따라서 음의 사이클을 감지하는 것이 필요하다 !
• dist[i][i]는 i에서 시작해서 i로 돌아오는 최단 경로를 의미한다. 초기화 할 때 dist[i][i]=0으로 설정된다. 그런데 플로이드 와샬을 다 돈 후에 이것이 음수라면, 음의 사이클이 존재한다고 판단한다.
  • 왜냐하면 i에서 출발해서 i로 돌아오는 경로의 총 가중치가 음수이라는 뜻이기 때문이다. 2가지 경우가 존재할 수 있다.
    • 직접적인 음의 사이클: 노드 i에서 시작하여 다시 노드 i로 돌아오는 경로에 음의 사이클이 존재하는 경우.
    • 간접적인 음의 사이클: 여러 정점을 거쳐 다시 노드 i로 돌아오는 경로에 음의 사이클이 포함된 경우.

# 음의 사이클 감지
for i in range(n):
    if dist[i][i] < 0:
        print("Graph contains a negative weight cycle")
        return None

구현

def floyd_warshall(n, graph):
    # 거리 테이블 초기화
    dist = [[int(1e9)] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    for u in range(n):
        for v, w in graph[u]:
            dist[u][v] = w

    # 플로이드 워샬 알고리즘
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # 음의 사이클 감지
    for i in range(n):
        if dist[i][i] < 0:
            print("Graph contains a negative weight cycle")
            return None

    return dist

# 예제 그래프
n = 4
graph = [
    [(1, 1), (2, 4)],
    [(2, -3)],
    [(3, 2)],
    [(0, -1)]
]

distances = floyd_warshall(n, graph)
if distances:
    for row in distances:
        print(row)