[알고리즘] 플로이드 와샬(Floyd Warshall) 알고리즘 정리

0. 플로이드 와샬(Floyd-Warshall) 알고리즘이란? 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)은 가중 그래프 (Weighted Graph)에서 발생하는 모든 경로에 대한 최단 경로를 찾는 알고리즘입니다. 다익스트라와 다르게 음의 가중치를 갖는 간선(Edge) 가 있어도 최단 경로 탐색이 가능하지만, 음의 사이클이 발생하는 경우에는 최단 경로를 탐색할 수 없습니다. 플로이드 와샬 알고리즘의 경우 dynamic programming(동적 계획법) 기법을 사용해서 구현하며, 시간 복잡도의 경우 그래프의 노드 개수가 N 개라고 가정했을 때, O(N^3)의 시간 복잡도를 갖습니다. 플로이드 와샬 알고리즘의 핵심 개념은 "이 정점을 거쳐가는 경우와 거쳐가지 않는 경우 중 어떤 경우가 더 최단 거리일까?"입니다. 1. 플로이드 와샬 알고리즘의 흐름 정리 아래 그래프를 예로 들어서 설명해 보도록 하겠습니다. 위 그래프에 따라 2차원 배열 형태로 각 출발점에서 ...

원문링크 : [알고리즘] 플로이드 와샬(Floyd Warshall) 알고리즘 정리