목록플로이드-워셜 알고리즘 (1)

민규의 흔적

[알고리즘] 플로이드-워셜(Floyd-Warshall) 알고리즘 [백준 11404번 - 플로이드]

2023년 10월 27일 플로이드-워셜(Floyd-Warshall) 플로이드-워셜 알고리즘이란, 모든 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면, 플로이드-워셜 알고리즘은 한 번의 실행으로 모든 정점 간의 최단 거리를 구할 수 있다는 차이로 구분할 수 있다. 또한 음수 가중치가 존재하는 가중치 그래프에서는 적용할 수 없는 다익스트라 알고리즘과는 다르게, 플로이드-워셜 알고리즘은 음수 가중치가 존재하는 가중치 그래프에서도 활용할 수 있다. 접근 방법 사전 준비 플로이드-워셜 알고리즘을 적용하기 위해선, 가중치 그래프가 존재해야 한다. 임의의 가중치 그래프를 예시로 들어보겠다. 정점은 1~5번까지 총 5개의 정점이 존재하고,..
알고리즘 2023. 10. 27. 22:26
이전 Prev 1 Next 다음