플로이드 워샬

1. 플로이드 워샬이란? Dijkstra와 달리 2. 구현 DP로 접근하기 위해 부분 문제를 정의해야 한다. n개의 노드를 가진 그래프에서 플로이드 워샬 알고리즘을 통해 각 노드 간의 최단 거리를 구하는 예시 코드다. INF는 무한을 의미하는 값으로 설정하였고, graph는 그래프를 나타내는 2차원 배열입니다. 플로이드-워샬에서 핵심 아이디어는 경유지를 하나씩 추가해 가며 비용을 최적화하는 것이다. 마지막 경유지를 추가하는 시점에서는 모든 … 더 읽기