파이썬(python) 알고리즘 - 최단 경로 (플로이드 워셜)

---

플로이드 워셜

---

개요

---

 

항목	내용
언제 쓰는가?	양방향이면서 음/양 가중치 그래프에서 최단 경로 찾기 모든 노드에서 다른 모든 노드 까지의 최단 경로의 길이 계산 ex) A→B로 가는 경로가 있는지 확인 ex) A→??지점을 거쳐서 B,C로 각각 갈때 최소비용 노드 개수가 500개 이하
그래프 유형	양방향, 가중치 (음의 사이클 x)
가중치	양(o), 음(o)
시간 복잡도	O(V^3), (V<=500)
알고리즘 분류	다이나믹 프로그래밍
사용 자료구조	배열

 

구현

---

항목	내용
자료구조 생성, 초기화	1. INF 값 설정 INF = 노드개수 * 최대가중치 +1  2. 최단거리 테이블 전체를 INF 로 초기화 arr = [[INF] for j in range(n)] for i in range(n)] 3. 자기 자신으로 향하는 비용은 0으로 초기화 for i in range(n):     arr[i][i] = 0 4. a→b, b→a 로의 비용 입력 for c,d,cost in fares:     arr[a-1][b-1] = cost     arr[b-1][a-1] = cost
메인 로직	1. 3중 포문 수행하며 DP테이블(arr) 갱신 for k in range(n):     for i in range(n):         for j in range(n):             arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

 

INF 값은 무엇으로 해야 하나요? 

---

INF = 노드개수 * 최대가중치 +1 

이유
1~N모드에서 모든 노드로 최대가중치로 이동하는 경우 - 자기자신으로 이동하는 경우 보다 큰 값으로 잡아야 버틸 수 있음. 위의 식은 안전한 값을 공식화 한 것

 

이렇게 하면 안됩니다.

1. INF = sys.maxsize : 연산에 시간이 오래걸려서 시간초과 발생 가능
   32bit(2^31-1) = 2147483647 (21억)
   64bit(2^63-1) = 9223372036854775807 (1000해)
2. int(1e9) : 극단적인 케이스에서 버틸 수 없음
   모든 노드로 이동할 때 모든 가중치가 최대가중치로 들어온 경우, 10억이 넘을 수 있음.

 

코드

---

INF = n*100000+1
fares = c→d로가는 비용이 cost인 인접리스트

arr = [[INF for j in range(n)] for i in range(n)]
for i in range(n):
    arr[i][i] = 0

for c,d,cost in fares:
    arr[c-1][d-1] = cost
    arr[d-1][c-1] = cost

for k in range(n):
    for i in range(n):
        for j in range(n):
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

 

관련 문제

---

11403번: 경로 찾기

 

응용

---

플로이드 워셜 알고리즘으로 사이클 형성여부 확인이 가능하며,

최소 비용을 갖는 사이클 값을 알아낼 수 있다.

 

플로이드 워셜 알고리즘을 수행한 최소 경로 테이블은 다음과 같은 의미를 가진다

1. 자기 자신으로 향하는 arr[i][i]을 0으로 초기화 하지 않고 INF로 둔 상태에서 플로이드 워셜 수행 시
   결과에 INF가 아닌 다른값이 들어있다면 나 자신으로 돌아왔다 (사이클 형성했다)는 뜻이다.
2. arr[i][j] 는 i에서 출발하여 여러 경로를 거쳐서 j까지 도달한 것 중의 최소 비용이다.
   arr[i][j] = i → j 가 아니라 i → ... → j
   arr[i][j] = j → i 가 아니라 j → ... → i
   즉, 사이클을 형성하는 경우 arr[i][j] + arr[j][i] 의 최소값이 최소 사이클 비용이다.
   
   

1956번: 운동

import sys
n, e = map(int, sys.stdin.readline().split())
INF = n*e+1
arr = [[INF]*n for _ in range(n)]
for i in range(e):
    a,b,c = map(int, sys.stdin.readline().split())
    arr[a-1][b-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j])

min_cycle_dist = INF
for i in range(n):
    if arr[i][i] != INF:
        for j in range(n):
            min_cycle_dist = min(min_cycle_dist, arr[i][j]+arr[j][i])
if min_cycle_dist == INF:
    min_cycle_dist = -1
print(min_cycle_dist)