[알고리즘] 플로이드-와샬, Floyd-Warshall

백준 문제를 풀다가 플로이드-와샬 문제를 또 마주쳤다. 몇 번 풀어본적 있는 유형임에도 플로이드 와샬이 뭐더라... 싶더라. 인간은 망각의 동물이구나... 플로이드-와샬 알고리즘 모든 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘 시간 복잡도 O(v^3) 음수 사이클이 없는 그래프에 적용됨 음의 가중치 허용 플로이드-와샬(Floyd Warshall) vs. 다익스트라(Dijkstra) 다익스트라 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (S.S.S.P - Single Source Shortest Path) 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직 우선순위 큐 + BFS의 형태 시간 복잡도 O(..

원문링크 : [알고리즘] 플로이드-와샬, Floyd-Warshall