Shortest Path in DAG 사이클이 없는 방향 그래프의 최단 경로 * DAG (Directed Acyclic Graph) - "사이클이 없는 방향 그래프"의 약자이다. - DAG에서는 모든 정점을 한 줄로 늘어놓으면, 뒤에 위치한 정점부터 앞에 위치한 정점으로 가는 간선은 존재하지 않도록 하는(=역방향으로 가지 못하는) 정점들의 순열이 존재한다. - DAG에서 이러한 순열은 위상 정렬을 통해 얻을 수 있다. - DAG의 경우, 간선들의 가중치의 부호를 모두 바꾸어 수행하면 최장 경로까지도 계산해낼 수 있다. (반면, 벨만-포드, 다익스트라 알고리즘에서는 최장 경로를 계산해낼 수 없다.) - DAG를 넘어서, 일반적인 그래프에서 최장 경로를 구하는 문제는 NP-Complete에 해당되는 문제이다..
Johnson's Algorithm 존슨 알고리즘 - Bellman-Ford Algorithm (URL)과 Dijkstra's Algorithm (URL)을 Subroutine으로 사용하여 Weighted Graph에서 존재할 수 있는 모든 (출발 정점, 도착 정점) Pairs에 대한 최단 경로를 계산해내는 알고리즘이다. - Sparse Graph에 대해서는 Floyd-Warshall Algorithm (URL) 보다 우수한 성능을 보여준다. - Time Complexity of Floyd-Warshall Algorithm : \(\Theta(|V|^3)\) - Time Complexity of Johnson's Algorithm : \(O(|V|^2\log |V| + |V|*|E|)\) * Graph ..
Floyd-Warshall Algorithm 플로이드-워샬 알고리즘 - 그래프 상에서, 존재할 수 있는 모든 (출발 정점, 도착 정점) Pairs에 대한 최단 경로를 Dynamic Programming 기법을 적용하여 계산해내는 알고리즘이다. - Warshall이 Directed Graph에서 정점들 간의 상호 연결 경로의 존재 여부를 밝히는 알고리즘을 제안하고, Floyd가 이를 변형하여 최단 경로를 찾아내는 알고리즘으로 만들었다. (즉, Warshall의 기여가 더 크다.) * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, Vertex로 대상이나 개체를 ..
Bellman-Ford Algorithm 벨만-포드 알고리즘 - Negative Weight를 허용하는 Weighted Graph상에서 Shortest Path를 찾아내는 알고리즘이다. - 음의 가중치는 허용하되, 가중치의 합이 음수인 Cycle은 허용되지 않는다. (가중치의 합이 음수인 Cycle을 몇 번이고 돌아서, 가중치의 합을 무한정 낮출 수 있기 때문이다.) - 간선을 최대 1개 사용하는 최단 경로, 간선을 최대 2개 사용하는 최단 경로, \(\cdots\), 이런식으로 간선을 최대 \(n-1\)개 사용하는 최단 경로까지 계산해나간다. * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 ..
Dijkstra's Algorithm 다익스트라 알고리즘 - 0 이상의 Weight만을 허용하는 Weighted Graph상에서 Shortest Path를 찾아내는 알고리즘이다. (가중치가 음수인 경우는 Bellman-Ford Algorithm (URL)으로 해결할 수 있다.) - 다익스트라 알고리즘은 시작 정점에서 다른 모든 정점까지의 간선들을 Greedy선택하며 계산해나간다. - Prim's Algorithm (URL)과 유사한 알고리즘 구조를 갖고 있다. * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, Vertex로 대상이나 개체를 표현하고, Edge..
Topological Sorting 위상 정렬 - DAG(Directed Acyclic Graph; 유향 비순환 그래프) \(G = (V, E)\)에서 \(V\)의 모든 정점을 정렬하되, 간선 \((i, j)\)가 존재하면 정렬 결과에서 정점 \(i\)는 반드시 정점 \(j\)보다 앞에 위치하게 정렬하는 방법을 의미한다. - Cycle이 있는 그래프에서는 위상 정렬을 수행할 수 없다. * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, Vertex로 대상이나 개체를 표현하고, Edge로는 이들 간의 관계를 표현한다. Examples of Algorithm us..
Kruskal's Algorithm 크루스칼 알고리즘 - Graph상에서 Minimum Spanning Tree(최소 신장 트리)를 구성하는 방법 중 하나이다. - Weight값이 가장 작은 간선(=Light Edge; 경량 간선)들을 집합에 포함시켜 가면서 신장 트리를 구성한다. - 이 때, 선택한 간선으로 인해 Cycle이 생긴다면, 해당 간선은 집합에 포함시키지 않는다. - \(n\)개의 정점으로 최소 신장 트리를 구성한다면, Kruskal's 알고리즘에서는 \(n-1\)개의 간선을 선택할 때 까지 연산을 진행해야 한다. - \(n\)개의 정점들을 모두 노드가 하나인 개별적인 트리로 본다면, Kruskal's 알고리즘에서는 \(n\)개의 트리로 구성된 Forest에서 두 트리를 하나로 합쳐가며 하나..
Prim's Algorithm 프림 알고리즘 - Graph상에서 Minimum Spanning Tree(최소 신장 트리)를 구성하는 방법 중 하나이다. - 시작 정점으로부터 Weight값이 가장 작은 간선과 연결된 정점을 선택해가며 신장 트리를 구성한다. - 이 때, 선택한 정점으로 인해 Cycle이 생긴다면, 해당 정점은 집합에 포함시키지 않는다. * Prim's 알고리즘은 하나의 집합에 정점을 더해가며 하나의 신장트리를 만드는 방식이고, Kruskal's 알고리즘은 여러 집합을 합쳐가며 하나의 신장트리를 만드는 방식이다. * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구..
