[최단 경로] 9 - 1 (2)플로이드 워셜 최단 경로 알고리즘

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용
• 다익스트라처럼 단계마다 '거쳐 가는 노드'를 기준으로 수행되지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.
• 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2) 의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. ➡ 총시간 복잡도 O(N^3)
• 
  

  	다익스트라	플로이드-워셜
  최단 거리 테이블	1차원 리스트	2차원리스트
  방법	매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾음	매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾지 않음
  전체 시간 복잡도	O(ElogV)	O(N^3)
  구분	그리디	다이나믹 프로그래밍

플로이드 워셜 점화식

✔  'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신한다.

🔆 '바로 이동하는 거리' > '특정한 노드를 거쳐서 이동하는 거리' ➡ 더 짧은 것으로 갱신한다.

 

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드 개수, 간선 개수 입력받기
n = int(input())
m = int(input())

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 자기자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, -1 출력
        if graph[a][b] == INF:
            print(-1, end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

 

입력 예

4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

 

출력 예 

0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0