서론 Floyd Warshall 알고리즘은 최단 경로를 구하는 방법중 하나이다. 동적계획법으로 접근하는데 시간 복잡도는 O(N^3)이다. 최단경로 구하는 알고리즘인 dijkstra와 비교하자면 간선 수가 많으면 Floyd 가 빠를 수 있다. 시작 정점이 정해져 있으면 dijkstra가 당연히 빠르다. 음의 가중치가 존재한다면 dijkstra는 사용할 수 없지면 Floyd는 사용가능하다. 구현 코드 for i in vertex // 경유 for j in vertex //시작점 if i == j continue for k in vertex //도착점 if i == j or j==k continue arr[j][k] = min(arr[j][i] + arr[i][k] , arr[j][k]) 문제에 적용 문제 :..