yoongrammer

목차플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 알아보기플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로(Shortest path) 문제 중에 모든 정점 쌍(All-pairs)에 대해 최단 거리를 구하는 알고리즘입니다. 플로이드 와셜 알고리즘은 Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, 또는 WFI algorithm 이라고도 합니다. 특징Dynamic Programming을 사용합니다.유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다.그래프에 음수 사이클 여부를 확인할 수 있습니다.구현플로이드 와셜 알고리즘은 각각의 정점 쌍을..

목차벨만-포드 알고리즘(Bellman-Ford Algorithm) 알아보기벨만-포드 알고리즘 (Bellman-Ford Algorithm)은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다.https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념목차   최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로yoongrammer.tistory.com 특징brute force strateg..

목차다익스트라 알고리즘 (Dijkstra's Algorithm) 알아보기다익스트라(Dijkstra) 알고리즘은 최단 경로(Shortest path) 문제 중에 Single-source path 찾는 알고리즘입니다. 최단 경로 문제는 아래 글을 참고하시기 바랍니다.https://yoongrammer.tistory.com/87 최단 경로(Shortest path) 문제 개념목차   최단 경로(Shortest path) 문제 알아보기 최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로yoongrammer.tistory.com 특징음수 가중치를 가진 간선이 없어야 합니다.탐욕 알고리즘(gree..

목차 최단 경로(Shortest path) 문제 알아보기최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다.여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로를 말합니다. 경로 p = 의 가중치(w) 합이 다음과 같다면$$ w(p) = \sum_{i=1}^k w(v_{i-1},v_{i}) $$정점 u에서 v까지의 최단경로 값은 다음과 같이 표시합니다.$$ \delta(u,v) = \begin{cases} min\{w(p) : u \overset{p}\rightsquigarrow v \}, & \mbox{if u에서 v로 가는 경로가 있다면} \\ \infty, & \mbox{if u에서 v로 가는 경로가 없다면} \end{cases}$$ ..

목차 위상 정렬(Topological sort) 개념 및 구현비순환 방향 그래프 (DAG: Directed Acyclic Graph)Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다. DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다. 위상 정렬(Topological sort)위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다.모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됩니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다.그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다..