[백준] 11404번 플로이드 워셜 알고리즘 설명 - 파이썬 with python

백준 11404번 문제는 제목도 플로이드, 코드도 플로이드 알고리즘을 쓰면 된다.

 

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

 

문제

 

 

설명

 

플로이드 워셜 알고리즘의 핵심 이론은 출발지점에서 도착지점까지 최단 경로가 있을때,

최단 경로 위에 경유지가 있다면 출발지점~경유지, 경유지~도착지점도 최단 경로가 된다.

그래서 플로이드 워셜 점화식은 D[s][e] = min(D[s][e], D[s][k] + D[k][e]) 가 된다.

 

1. 출발지점과 도착지점이 같으면 0, 다르면 무한대로 초기화한다.

2. 최단거리 이중리스트에 input 값을 넣어준다.

3. 점화식으로 최단거리 리스트를 업데이트 한다.

 

※ 플로이드 워셜 알고리즘 로직은 외우도록 한다.

for 경유지 k (노드갯수):
    for 출발지점 s (노드갯수):
        for 도착지점 e (노드갯수):
            D[s][e] = min(D[s][e], D[s][k] + D[k][e])

 

코드

 

import sys
input = sys.stdin.readline

city, bus = int(input()), int(input())
D = [[float('inf')]*city for _ in range(city)]

# 인접 행렬 생성
for _ in range(bus):
    s, e, cost = map(int, input().split())
    s -= 1
    e -= 1
    if D[s][e] > cost:
        D[s][e] = cost

# 플로이드 워셜
for k in range(city):
    D[k][k] = 0
    for start in range(city):
        for end in range(city):
            if D[start][end] > D[start][k] + D[k][end]:
                D[start][end] = D[start][k] + D[k][end]

for dist in D:
    for idx in dist:
        if idx != float('inf'):
            print(idx, end=' ')
        else:
            print(0, end=' ')
    print()

 

 

최단 거리 알고리즘 다익스트라, 벨만 포드, 플로이드에 대한 차이점과 자세한 설명은 알고리즘 카테고리에 정리해뒀습니다.