플로이드 워셜

** 정의

모든 지점에서 다른 모든 지점까지 최단거리

핵심 개념은, 한 지점에서 다른 지점까지 이르려면, 바로 가거나, 어딘가를 경유하거나이다.

 

따라서 위의 가설은 전제로 한다.

 

**구현

4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

테스트 케이스

 

 

import sys
from collections import defaultdict
from pprint import pprint

from min_cost.floyd_warshall import floyd_warshall

with open('testcase_fw.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

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

    graph = defaultdict(list)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

    pprint(floyd_warshall(graph))

입력 값 가공 및 함수 호출

 

 

 

INF = int(1e9)

def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

실제 플로이드 워셜 구현 함수

 

** 관련 문제

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

11404번: 플로이드