동빈나 2021 이코테 _ 7. 최단경로 알고리즘 (플로이드 워셜)

• 모든노드에서 다른 모든노드까지의 최단경로를 계산한다.
• 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.
  • 다만 매 단계마다 방문하지 않은 노드중 최단거리를 갖는 노드를 찾는 과정이 필요없다.
• 2차원 테이블에 최단거리 정보를 저장한다. 
• DP유형에 속한다.
•  

---

플로이드 워셜 알고리즘  

• 노드의 개수가 많은경우에는 플로이드워셜보다 다익스트라를 사용하는것이 좋다.
• 시간복잡도는 O(n^3)임

행은 출발노드, 열은 도착노드를 의미함.

k값만 바꿔가면서 모든a,b를 반복하며 전부 확인해주면 된다.

k = 1일때(1번노드를 거치는) 모든 a,b에 대해서 확인하고 갱신한다.

 소스코드

import sys
input = sys.stdin.readline

INF = int(1e9)

n = int(input()) #노드
m = int(input()) #간선

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 = map(int, input().split())
    graph[a][b] = min(graph[a][b], c) # 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):
        if graph[a][b] == INF:
            print(0, end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

• 성능분석 : 각 단계마다 엔제곱의 연산을 통해 현재 노드를 거쳐가는 모든경로를 고려하는데, 이때 현재노드또한 n개로 변해가므로 n의 세제곱의 시간복잡도를 갖는다.