[Algorithm] 플로이드-워셜(floyd-warshall) 알고리즘 (python)

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 최단 거리를 구할 때 사용하는 알고리즘이다.

벨만-포드 알고리즘과 같이 음수 가중치를 가지는 노드가 있어도 사용가능하다. 하지만 벨만-포드 알고리즘보다 더 큰 시간 복잡도를 가진다.

 

플로이드-워셜 알고리즘의 핵심 원리는 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합이라는 것이다.

 

 

 

파이썬으로 플로이드-워셜 알고리즘 구현하기

1. 최단 거리를 저장할 2차원 리스트 선언

출발 노드와 도착 노드가 같은 경우는 0으로 초기화하고 기본은 시스템 최댓값으로 초기화한다.

dist=[[sys.maxsize]*(n+1) for _ in range(n+1)] 

for i in range(1, n+1):
    dist[i][i]=0

 

2. 주어진 그래프 값 저장

1에서 선언한 2차원 리스트에 그래프 값을 저장한다.

for _ in range(m):
    a, b, c=map(int, sys.stdin.readline().split())
    dist[a][b]=c

 

3. 최단 거리 리스트 업데이트

플로이드-워셜 알고리즘의 핵심 원리인 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합이라는 것을 이용해 최단 거리 리스트를 업데이트한다. 3중 for문을 사용해서 해당 부분을 구현한다. 경유지 k, 출발지 s, 도착지 e 순으로 반복한다.

for k in range(1, n+1):
    for s in range(1, n+1):
        for e in range(1, n+1):
            dist[s][e]=min(dist[s][e], dist[s][k]+dist[k][e])

 

플로이드-워셜 알고리즘을 활용한 문제

https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

 

참고한 책 : Do it! 알고리즘 코딩테스트 파이썬편