플로이드 워셜 : Floyd Warshall

최단경로 알고리즘 중 플로이드 워셜

O(n**3)으로 노드 수가 적을 때 쓸 수 있다

하나의 정점에서 다른 정점까지의 최단거리를 구한다

 

 

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for i in range(1, n + 1):
    graph[i][i] = 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])

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

• 위의 소스는 아래의 깃허브를 참고했으나 0으로 초기화하는 부분을 단순화
• graph[a][b]에는 a에서 b까지의 최단 거리가 저장된다
• DP의 일종으로 점화식이 있다
  graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
• k는 거쳐가는 노드
• 다익스트라가 시작점( 1 )에서 다른 모든 노드( n )로의 최단거리로 "일대다"라면
  플로이드 워셜은 "다대다"이다
• 노드 수가 500개 이하에서 가능

의문이었던 점

2->5 노드 까지의 거리의 최소를 어떻게 2->4 + 4->5라고 확신할 수 있는 것인지 처음에 의아했다

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이 그림을 보고 조금 깨닫게되었다 k=1일 때 알게된 최단 경로를 계속해서 다시 사용하기 때문에 이리저리 돌고돌아 결국 universe..⭐(머리로 깨닫고 말을 못 하겠다..)

빨간 박스가 k=2에도 나오고 k=3에도 나오는 것을 볼 수 있다. 그래서 최단 경로가 완성 된다

 

음수 사이클

음수사이클이 있는지 확인할 수 있다.

graph의 대각행렬(자기 자신에 대한 비용,원래는 0이어야 함)이 음수면 음수사이클이 있다

다익스트라의 경우 음수 사이클이 있으면 알고리즘이 무한으로 돌게 된다.