AncomWiki

2024-05-07 일기: 플로이드-워셜 알고리즘 학습

Properties1
description지진 악몽을 꾸고 난 후, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 접했다. 모든 지점 간 최단 경로를 구하는 DP 알고리즘으로, 3중 루프와 점화식 D(a,b) = min(D(a,b), D(a,k) + D(k,b))을 통해 구현됨을 확인했다.

25 min read

2024-05-07 일기: 플로이드-워셜 알고리즘 학습

Source

  • Basic Journals/Daily Journals/2024 갑진년/갑진년 128일, 5월 7일 화요일.md

Summary

지진 악몽을 꾸고 난 후, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 접했다. 모든 지점 간 최단 경로를 구하는 DP 알고리즘으로, 3중 루프와 점화식 D(a,b) = min(D(a,b), D(a,k) + D(k,b))을 통해 구현됨을 확인했다.

Key Points

  • 플로이드-워셜 알고리즘은 모든 노드 쌍 간의 최단 경로를 계산한다.
  • 동적 계획법(DP) 기반이며, 3중 루프 구조를 가진다.
  • 핵심 점화식: D(a,b) = min(D(a,b), D(a,k) + D(k,b))

그래프 뷰