목록2024/12/03 (1)
우당탕탕 개발일지
[BOJ] 플로이드 워셜
플로이드 워셜이란 그래프 최단 경로를 구하는 알고리즘 중 하나로, 모든 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘이다. 플로이드 워셜 알고리즘의 점화식은 다음과 같다. 다익스트라 알고리즘과 비슷해보이지만, 소스코드가 다익스트라에 비해 짧고 구현이 쉽다. 다익스트라 알고리즘단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다.1차원 리스트에 저장한다. 플로이드-워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 거리를 저장한다.2차원 테이블에 저장한다.for (int k = 0; k [ BOJ 11403 ] 경로 찾기https://www.acmicpc.net/problem/11403 처음에는 그래프 인접 리스트로 만들어 풀이를 하였으나 간과한 부분이 있었다. 1. 경로 탐색i → ..
알고리즘
2024. 12. 3. 15:36