최단경로 - 3
Floyd-warshall 알고리즘 : all to all - 가중치 방향 그래프 G=(V,E), V={1,2,...,n} - 모든 노드 쌍들간의 최단경로의 길이를 구함 - d^k[i,j] : 중간에 노드집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이 i와 j가 바로 연결 첫 번째 : 연결 두 번째 : 연결 x n개의 노드가 있으므로 i에서 j로 갈 때 n개의 노드를 거쳐서 감 k를 거치지 않고 간다면 d^k-1[i,j] k를 거쳐서 간다면 d^k-1[i,k] + d^k-1[k,i] 따라서 위의 두 값 중 최솟값을 고르면 된다. 수도코드 - 1 수도코드 - 2 경로 찾기 - 파이 이차원 배열을 만들어준다 - k를 거쳐서 가게 된다면 파이 배열에 k를 넣어준다 경..
2021. 3. 30.
최소비용신장트리 -2
kruskal 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다 - 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다 - n-1개의 에지가 선택되면 종료한다. - 가중치가 작은 순서대로 연결하면서 순환이 되면 연결하지 않는다. 순환여부 확인 - 초기 상태 : 선택된 에지 없음 - 각각의 연결요소를 하나의 집합으로 표현 {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i} -> {a}, {b}, {c}, {d}, {e}, {f}, {g, h}, {i} -> {a}, {b}, {c, i}, {d}, {e}, {f}, {g, h} -> {a}, {b}, {c, i}, {d}, {e}, {f, g, h} -> {a, b}, {c, i..
2021. 3. 24.
