profile
Programmer
post-thumbnail

플로이드 와샬(Floyd-Warshall) 알고리즘

그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 O(V^3)시작점에 대한 모든 노드들의 최단거리를 구하는 다익스트라 알고리즘과 달리 모든 쌍에 대한 최단 거리를 구하고, 음의 가중치를 가지는 그래프에도 쓸 수 있다는 것이 특징이다

2021년 6월 1일
·
0개의 댓글
·