Seongwon Lim

서론 이번 글에서는 모든 정점 사이의 최단 경로를 구하는 알고리즘인 플로이드-워셜(Floyd-Warshall) 알고리즘의 개념을 살펴보고 예제를 알고리즘의 동작 원리를 알아보고자 한다. 또한, 파이썬을 통해 해당 알고리즘을 구현하는 방법을 살펴볼 것이다. Floyd-Warshall Algorithm 플로이드 워셜 알고리즘은 그래프(Graph) 상에서 가능한 모든 노드 쌍에 대한 최단 거리를 구하는 알고리즘으로, 최단 경로 알고리즘 (Shortest Path Algorithm) 이라고도 불린다. 특정 정점에서 모든 정점까지의 최단 거리를 구하는 다익스트라(dijkstra) 알고리즘과 다른 점은 다음과 같다. 모든 노드 쌍에 대한 최단 거리를 구할 수 있다. 간선의 가중치가 음의 값을 가질 수 있다. 플로이..