반응형 114041 파이썬(Python) 플로이드-워셜(Floyd-Warshall) 개념과 예제 (백준 11404) 플로이드-워셜 알고리즘 ● 다익스트라( O(ElogV) ) vs 벨만-포드 ( O(EV) ) vs 플로이드-워셜 ( O(V^3) ) 다익스트라는 양수엣지에서 가장 빠르게 최단거리를 구하는 알고리즘이고, 벨만-포드는 음수엣지에서 최단거리를 구하는 알고리즘이라면, 플로이드는 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. (플로이드-워셜 알고리즘은 음의 간선도 사용할 수 있습니다) 그러므로 한노드에서 출발하는 최단거리를 구하라고 하면 오래 걸리지만, 출발노드가 계속 달라지면서, 최단거리의 질의가 많아지면 빛을 발하는 알고리즘이라고 볼 수 있습니다. 동적계획법(DP)의 원리를 이용한 알고리즘으로 점화식은 아래와 같습니다. s에서 시작해서 e로 간다고 하겠습니다. s->k->e 방식으로 k를 경유.. 2022. 12. 31. 이전 1 다음
