플로이드-와샬 알고리즘

플로이드-와샬 알고리즘

💡모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

• 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘 수행 BUT 방문체크 필요 없음
• 2차원 테이블에 최단 거리 정보 저장해서 점화식을 통해 갱신해나가는 dp유형
• 시간복잡도 O(V^3) -> 노드가 500개 이상이면 시간초과 날 수도

원리

각 단계마다 특정한 노드 K를 거쳐 가는 경우를 확인
-> a에서 b로 가는 최단 거리보다 a에서 K를 거쳐 b로 가는 거리가 더짧은지 검사

D(a, b) = min(D(a,b), D(a,k) + D(k, b))

알고리즘

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

1. 2차원 리스트를 큰값으로 초기화
2. 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
3. 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
   -> g[출발][도착] = 비용
4. 1~N번 노드를 '거쳐'가는 비용과 원래 비용을 비교하여 업데이트
5. 모든 노드에서 모든 노드까지 가는 최소비용을 구할 수 있음

코드

# 11404 플로이드 - 골드4 김수민
N = int(input())
M = int(input())
cost = [[1e9] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    start, end, dis = map(int, input().split())
    cost[start][end] = min(dis, cost[start][end])

# 플로이드-와샬 알고리즘
for k in range(1, N + 1):
    cost[k][k] = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

# 출력
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if cost[i][j] == 1e9:
            cost[i][j] = 0
        print(cost[i][j], end=' ')
    print()

[참고]
https://freedeveloper.tistory.com/385