플로이드-와샬(Floyd-Warshall) 알고리즘 (백준 문제 포함)

다익스트라 알고리즘 같은 경우에는 하나의 정점에서 출발해서 모든 정점으로의 최단거리를 구할 수 있는 반면에,

플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구할 수 있다.

이 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단거리를 구한다는 점이다.

다익스트라에 비해서 구현 난이도가 훨씬 쉽다! 와!! 삼중 반복문!!!

 

아래 코드는 파이썬으로 구현한 플로이드-와샬 알고리즘 예시이다.

백준 11404번 플로이드)

import sys
INF = sys.maxsize
input = sys.stdin.readline

n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < dis[a-1][b-1]:
        dis[a-1][b-1] = c
for k in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
    for j in range(n):
        if dis[i][j] == INF:
            dis[i][j] = 0
for t in dis:
    print(*t)

 

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1017?category=911939

백준 알고리즘 11404번 플로이드(python)

jinho-study.tistory.com/1019

백준 알고리즘 2458번 키 순서(python)

jinho-study.tistory.com/1020

백준 알고리즘 11403번 경로 찾기(python)

https://jinho-study.tistory.com/1085

프로그래머스 Level 3 순위