[Greedy] Floyd Algorithm
플로이드 알고리즘 최단거리를 찾는 알고리즘입니다. 한 노드를 고정시키고 나머지 노드들의 경로의 기존 값과 고정노드를 통한 값을 비교하고 수정합니다. 모든 노드를 거치면 완료됩니다. Ak[i,j] = min ( Ak-1[i,j] , Ak-1[i,k] + Ak-1[k,j] ) ex) A0 N1 N2 N3 N4 N1 0 7 ∞ 3 N2 2 0 ∞ ∞ N3 5 1 0 ∞ N4 8 ∞ 2 0 A1 = 1 고정 (1행 & 1열 & 대각 고정) 다른 노드들의 기존 값과 노드1을 거쳐가는 경우를 비교 A1[2,3] = min( A0[2,3], A0[2,1] + A0[1,3] ) = min( ∞, 2 + ∞ ) = ∞ A1[2,4] = min( A0[2,4], A0[2,1] + A0[1,4] ) = min( ∞, 2 +..
[Greedy] Prim's Algorithm
프림 알고리즘 최소 비용 신장트리를 찾는알고리즘 중 하나로 특정 시작점부터 { 연결될 수 있는 노드들중 최소비용 노드를 연결 } 을 반복합니다. 연결시 이미 만난 노드라면 연결하지 않습니다. 단점 : 연결되지 않은 두개의 트리가 있을 시에는 최소신장을 찾을 수 없습니다. ex) Start A (5, 13) -> 5 D 연결 A, D (7, 9, 13) -> 7 C 연결 A, D, C (5, 9, 13, 20) -> 5 E 연결 A, D, C, E (9, 13, 15, 20) -> 9 중복 -> 13 B 연결 A, D, C, E, B (8, 15, 20) -> 8 F 연결 A, D, C, E, B, F
