[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python)

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python)

 

 

↓ 플로이드 워셜 알고리즘에 대한 개념은 이전 게시글에 정리해두었다.

 

codingexplore.tistory.com/53

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

 

이번에는 파이썬 (Python) 으로 어떻게 플로이드 워셜 알고리즘을 구현할 것인가에 대한 것이다.

 

 

구현 - O(N^3)

INF = int(1e9)

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

graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단거리 테이블

for s in range(1, n + 1):
    for e in range(1, n + 1):
        if s == e: # 그래프의 시작지점 == 도착지점
            graph[s][e] = 0 # 거리 0으로 초기화

# S0 : 그래프 초기화
for _ in range(m):
    s, e, dist = map(int, input().split())
    graph[s][e] = dist

# S1 ~ SN : 모든 노드를 돌며 각 노드를 거치는 모든 경로 검토
for node in range(1, n + 1): # 노드에 대한 루프
    for s in range(1, n + 1): # 2차원 그래프 루프
        for e in range(1, n + 1):
            graph[s][e] = min(graph[s][e], graph[s][node] + graph[node][e])

# 출력
for s in range(1, n + 1):
    for e in range(1, n + 1):
        if graph[s][e] == INF:
            print("can not access", end = ' ')
        else:
            print(graph[s][e], 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

 

 

이번 구현의 핵심은 3중 for 문이 있는 부분이다.

# S1 ~ SN : 모든 노드를 돌며 각 노드를 거치는 모든 경로 검토
for node in range(1, n + 1): # 노드에 대한 루프
    for s in range(1, n + 1): # 2차원 그래프 루프
        for e in range(1, n + 1):
            graph[s][e] = min(graph[s][e], graph[s][node] + graph[node][e])

s 에서 현재 node를 거쳐 e 로 가는 최단거리

-> s 에서 node로 가는 최단거리 + node에서 e로 가는 최단거리

이렇게 두 부분으로 나누어서 더하면 현재 node 를 거치는 경로를 조사할 수 있다.

 

기존 최단거리 테이블인 graph[s][e] 와 새로운 최단거리인 graph[s][node] + graph[node][e] 를 비교하여

더 짧은 거리로 테이블을 갱신하면 된다.

 

코드 자체는 간단하지만 3중 for문을 사용하였기 때문에 시간복잡도는 O(N^3) 로 높다.