플로이드-워셜 모든 쌍 최단 경로
모든 두 정점 사이의 최단 경로를 찾습니다
플로이드-워셜 모든 쌍 최단 경로은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
모든 쌍을 한 번에
때로는 한 시작점에서가 아니라 모든 노드 쌍 사이의 최단 경로가 필요합니다. 이것이 모든 쌍 최단 경로 문제입니다.
플로이드-워셜 알고리즘
플로이드-워셜은 세 개의 간결한 중첩 반복문과 거의 별도의 설정 없이 모든 쌍에 대한 전체 거리 표를 채웁니다.
거리 행렬
dist[i][j]가 i에서 j까지의 현재 최선 비용을 나타내도록 행렬을 사용합니다. 주어진 직접 간선으로 행렬을 초기화합니다.
dist = [[INF] * n for _ in range(n)]대각선 설정하기
모든 노드는 비용 없이 자기 자신에 도달할 수 있으므로, 완화를 시작하기 전에 대각선의 dist[i][i]를 0으로 설정합니다.
for i in range(n):
dist[i][i] = 0중간 노드 아이디어
핵심은 경로가 중간 노드 k를 지나가도록 허용한 다음, k를 거쳐 가는 비용이 직접 가는 것보다 저렴한지 확인하는 것입니다.
반복문 순서가 중요합니다
바깥 반복문은 k이며, 선택한 중간 지점을 나타냅니다. 안쪽 반복문 i와 j는 그 중간 지점을 기준으로 모든 쌍을 시도합니다.
for k in range(n):
for i in range(n):
for j in range(n):완화 단계
각 쌍에 대해 k를 거쳐 완화합니다. i에서 k를 거쳐 j로 가는 경로가 더 짧으면 dist[i][j]를 그 비용의 합으로 갱신합니다.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]k를 바깥에 두는 이유
k에 대한 처리가 끝날 때까지 모든 쌍은 k 이하의 중간 노드를 사용할 수 있습니다. k를 가장 바깥에 두어야 이 조건이 올바르게 유지됩니다.
음수 간선도 괜찮습니다
플로이드-워셜은 음수 간선을 허용하지만 음수 사이클은 허용하지 않습니다. 음수 사이클이 있으면 일부 대각선 항목이 0보다 작아집니다.
실행 시간
n개의 노드에 대해 세 번 반복하므로 시간 복잡도는 O(n^3), 공간 복잡도는 O(n^2)입니다. n이 수백 정도일 때만 실용적입니다.
선택할 때
그래프가 작고 조밀하며 한 시작점이 아니라 모든 노드 쌍의 거리가 정말 필요할 때 플로이드-워셜을 선택합니다.
빠른 확인
플로이드-워셜에서 가장 바깥에 있어야 하는 반복문은 무엇인가요?
복습: 플로이드-워셜
행렬을 초기화하고 대각선을 0으로 만든 다음 k, i, j 순서로 반복하며 k를 거쳐 완화합니다. O(n^3) 시간에 모든 쌍의 최단 경로를 구할 수 있습니다. 🧮
자주 묻는 질문
“플로이드-워셜 모든 쌍 최단 경로” 강의는 무료인가요?
네 — “플로이드-워셜 모든 쌍 최단 경로” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“플로이드-워셜 모든 쌍 최단 경로”에서 뭘 배우나요?
모든 두 정점 사이의 최단 경로를 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“플로이드-워셜 모든 쌍 최단 경로” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 힙을 이용한 다익스트라
- 덱을 이용한 0-1 BFS
- 벨만-포드와 음의 간선
- 플로이드-워셜 모든 쌍 최단 경로