KalelPark's LAB

Bellman-Ford Algorithm 이란? 한 정점(Vertex)에서 다른 정점(Vertex)까지의 최단 거리를 구하는 알고리즘이다. 다익스트라(Dijkstra Algorithm)과 달리, 정점(Vertex) 간의 간선(edge) 비용이 음수인 경우에도 사용가능하다. 벨만 포드(Bellman-Ford)는 다이나믹 프로그래밍(Dynamic Programming)이라고도 할 수 있다. 그러한 이유는 매번 저장해놓은 최소 비용을 활용해서, 새로운 최소 비용을 갱신하기 때문이다. 벨만 포드(Bellman-Ford)는 다익스트라(Dijkstra Algorithm)보다 시간이 오래 걸리는데, 그러한 이유는 최소 비용을 가지는 간선(edge)만을 우선적으로 뽑는 다익스트라(Dijkstra Algorithm) 달..

Sollin's Algorithm 이란? 최소 비용 신장 트리를 구하는 알고리즘 중 하나로, Prim's Algorithm과 달리 간선(Edge)를 하나씩 선택하는 것이 아닌 동시에 여러 개의 간선(Edge)을 선택하여, Tree를 만드는 알고리즘이다. Sollin's Algorithm을 알기 전, Forest를 Sollin's Algorithm 동작 1. 각각의 단계마다, 신장 트리 집합 내 Vertex를 포함한 몇 개의 Edge를 선택합니다. (Prim's Algorithm, Kruskal's Alogrithm과 다르게, 2개 이상 Edge를 선택하는 것이 가능합니다.) 2. 각 트리는 다른 트리와 연결할 수 있는 최소 비용의 Edge를 선택합니다. (중복되는 Edge는 제거합니다.) * 만약, 비용..

Prim's Algorithm 이란? 최소 비용 신장 트리를 구하는 알고리즘 중 하나로, 가중치를 가지는 그래프에서, 가장 작은 가중치를 가지는 간선(Edge)를 시작으로 인접한 정점과 연결된 Edge들 중에서, 가장 작은 가중치를 가지는 간선(Edge)들을 선택하는 방식이다. Prim 알고리즘은, 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복됩니다. 그러므로 시간복잡도는 O(N*N) 입니다. Prim's Algorithm 동작 1. 시작 단계에서, 시작 정점만을 MST(최소 비용 신장 트리) 집합에 포함합니다. 2. MST(최소 비용 신장 트리) 집합에 포함된 정점들에 인접한 정점과 최소 간선으로 연결할 수 있는 정점을 집합에 넣어줍니다. 3. 이러한 과정을 간선이 N-1개, 즉 C..