알고리즘/Floyd-Warshall1 Floyd-Warshall 플로이드 워셜 문제 문제 1번부터 N번까지의 노드가 있는데 중간에 소개팅녀를 만나는 노드를 거쳐야 한다 따라서 n번 노드를 가야한다면 중간에 소개팅녀가 있는 k번 노드를 지나야 한다는 것 각 노드 사이는 양방향으로 갈 수 있고 1의 cost를 가진다 플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로 구하는 알고리즘 (cf. 다익스트라 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘) 2차원 배열을 사용하여 각 노드에서 다른 노드로 가는 모든 최단 거리를 구해야함 -> O(N^2)의 시간 복잡도가 필요 방문판매원이 1번 노드에서 4번 노드까지 최단거리로 방문해야 한다면 1번에서 출발하여 2번 노드를 경유해서 4번 노드로 가는 경우 1번에서 출발하여 3번 노드를 경유해서 4번 노드로 가는 .. 2021. 7. 30. 이전 1 다음