[플로이드 와샬] 백준 11404. 플로이드 (기본)

플로이드는,

다익스트라, 벨만 포드 알고리즘은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구한다. 하지만 모든 쌍 간의 최단 거리를 구하기 위해서 보다 빠르고 간단한 방법이 플로이드 이다.

모든 쌍에 대한 최단 거리 알고리즘

알고리즘 특징

• 경유점이 존재 목적지를 갈 때 중간에 다른 노드를 거치는 것이 더 비용이 적을 수 있음.
• graph[u][v] 정점 u에서 v로 가는 최단 거리를 저장
• 논리 자체는 어렵지 않았고, 플로이드는 중간 노드를 기준으로 for 를 세 번 돈다는 점 (중간 노드가 최상단 반복문)
• 그래서 그래프가 크지 않을 때 쓸 수 있다는 점 (시간 복잡도가 n**3)을 명심명심~
• 무한 값을 변수에 할당해서 쓰면 편함

핵심 구조

g = [[무한 값] for _ in range(노드수 + 1)]
for _ in range(노드수):
    출발노드, 도착노드, 가중치 = map(int, input().split())
    g[출발노드][도착노드] = 가중치 # 경로가 여러 개라면, 기존 값과 비교해서 할당



def Floyd():
    for mid in range(1,n+1):
        for x in range(1,n+1):
        	for y in range(1, n+1):
				if x==y:
                	g[x][y] = 0
                else:
                	g[x][y] = min(g[x][y], g[x][mid]+g[mid][y])
                    # 중간에 다른 노드를 거친 경로가 더 가까운 지, 이미 채워진 값이 가까운지,

# 다 돌면 갈 수 없는 곳은 무한 값 이상임. => 출력 시 0 처리만 해주면 됨
Floyd()
print(g)

가중치 = 거리

주요 변수

g (그래프)

inf (무한 값)

 

관련 문제

백준 11404 플로이드 (기본)

백준 2458 키 순서(응용)

백준 2252 줄 세우기(위상정렬 기본)

모든 최단 경로를 구하는 알고리즘

다익스트라는
하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (S.S.S.P - Single Source Shortest Path) 이었다면,

플로이드-워셜 알고리즘은
한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.
플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

풀이

import sys

sys.stdin = open("input.txt", "rt")

# 도시개수 node
n = int(input())

# 버스개수
m = int(input())
inf = 10**6
g = [[inf] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    g[a][b] = min(g[a][b], c)  # a - 비용c - b


for mid in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                g[i][j] = 0
            else:
                g[i][j] = min(g[i][mid] + g[mid][j], g[i][j])
for x in g[1:]:
    for gg in x[1:]:
        print(gg if gg < inf else 0, end=" ")
    print()

 

< 반성 - 조건을 다시 확인하자!>

마지막에 inf 랑 비교해서 출력하는 부분을, gg == inf 로 했어서 틀렸다,

무한보다 큰 수가 나오면 0 으로 출력하는 거였기 때문에, 같다로 하면 오답 처리!

 

 

플로이드 와샬 학습 참고 블로그 1

플로이드 와샬 학습 참고 블로그 2

플로이드 와샬 학습 참고 블로그 3

 

깃헙 코드