본문 바로가기

알고리즘14

16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3) 이전 강좌 첨부,, 16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3) 이전 강좌,,, Bellman-Ford Algo- 나 Dijkstra Algo-는 one-to-all 알고리즘이었다. 이번 강좌에서는 all-to-all 알고리즘에 대해 공부한다. all-to-all 알고리즘의 하나가 Floyd Algorithm 혹은 Floyd-Warshall Algorithm이다. Floyd-Warshall 알고리즘 - 가중치 방향 그래프 G=(V, E), V={1, 2, ..., n} (노드들에는 1번부터 n번까지 번호가 붙어 있다..) - 모든 노드 쌍들 간의 최단경로의 길이를 구함 - d의 k승[i, j] ㄴ 중간에 노드집합 {1, 2, ..., k}에 속한 노드들만 거쳐서 노.. 2021. 1. 10.

16-1강. 최단경로 (Shortest Path Problem) (1) 아이패드 굿노트를 사용해서 적은 필기 2021. 1. 6.

15-4. 최소비용신장트리( Minimum Spanning Tree) Prim의 알고리즘 - 임의의 노드를 출발노드로 선택 - 출발 노드를 포함하는 트리를 점점 키워 감 (크러스칼은 에지들의 가중치가 작은 순서대로 접근하는 방법이었다면, 프림은 출발노드부터 연결 연결된 노드들을 탐색하여 트리를 키운다) - 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 위의 그래프에서 출발 노드가 초록색 노드라고 하면, 출발 노드에 인접한 노드들을 A라 하면, 그 부분트리에 포함된 노드들의 집합은 V of A(빨간 노드들)라 하자. (a) : 출발노드 a 에서 인접한 노드 b와 노드 k 가 있다. 가중치가 작은 에지는 4이므로 노드 b를 선택한다. (b) : 이제 노드 a 와 노드 b는 V of A의 부분집합이 되었다. (c.. 2020. 12. 17.

15-2강. 최소비용신장트리 (Minimum Spanning Tree) (2) 최소비용신장트리 (Minimum Spanning Tree) Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다. - 에지들을 그 순서대로 하나씩 선택해 간다. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다. - n-1개의 에지가 선택되면 종료한다. 위의 그래프에서, 모른 에지들을 작은 것부터 큰 것 순으로 정렬해 두었다고 가정하자. (a) : 가장 가중치(weight)가 작은 에지(1)를 선택한다. => 내가 선택한 에지들은 cycle을 형성하지 않는다. (왜? 에지가 하나밖에 선택되지 않았으니까) (b) : 그 다음으로 가중치(weight)가 작은 에지(2)를 선택한다. => cycle을 형성하지 않는다. (c) : 그 다음으로 가중치(weight)가 작은 에.. 2020. 12. 13.

이전 1 2 3 4 다음

티스토리툴바