최단거리 찾기 3 - 플로이드-워셜(floyd-warshall) 파이썬, 백준 11404 파이썬

개요

그래프에서 최단거리를 구하는 알고리즘입니다. 특징은 아래와 같습니다.

• 모든 노드 간의 최단 거리 구하기 가능
• 음수 가중치 에지가 있어도 수행 가능
• 동적 계획법의 원리를 이용해 알고리즘을 구성
• 시간복잡도는 O(V^3)

구현 방법

시작 노드에서 도착 노드까지의 최단 경로를 구할 때 그 중간에 있는 노드 K가 존재한다면

시작 노드→K, K → 도착노드와 같은 부분 경로도 최단 경로라는 원리입니다.

sp_list[S][E] = min(sp_list[S][E], sp_list[S][K] + sp_list[K][E])

 

인접 행렬로 구현하는 방법입니다.

1. 리스트 선언 및 초기화
   • sp_list[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 리스트
   • S와 E가 같은 칸은 0, 다른 칸은 무한으로 초기화
2. 최단 거리 리스트에 그래프 데이터 저장
   • sp_list[S][E] = W로 에지의 정보를 리스트에 입력
3. 점화식으로 리스트 업데이트하기
   • 기존에 구한 점화식을 3중 for문 형태로 반복하며 리스트 값 업데이트
   • 경유지 K 관한 for문, 출발 노드 S에 관한 for문, 도착 노드 E에 관한 for문
     • 각 for문 크기는 (1~N)
     • sp_list[S][E] = min(sp_list[S][E], sp_list[S][K] + sp_list[K][E])

쓰이는 곳

• 모든 노드간의 최단거리를 확인하는 문제
• 노드 개수가의 범위가 다른 것에 비해 적게 나온 문제

---

백준 11404

import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
M = int(input())

# 값 초기화
d_list = [[sys.maxsize for j in range(N+1)] for i in range(N+1)]
for i in range(1, N+1):
    d_list[i][i] = 0

# 간선 입력
for i in range(M):
    s, e, w = map(int, input().split())
    d_list[s][e] = min(d_list[s][e],w)

def floyd_warshall():
    for k in range(1, N+1): # k가 가장 바깥쪽이어야 함
        for s in range(1, N + 1):
            for e in range(1, N + 1):
                d_list[s][e] = min(d_list[s][e], d_list[s][k] + d_list[k][e])

floyd_warshall()
for s in range(1, N+1):
    for e in range(1, N+1):
        if d_list[s][e] == sys.maxsize:
            print('0 ')
        else:
            print(str(d_list[s][e]) + ' ')
    print('\n')