studlog

Single source shortest pathunweighted graph → BFSweighted graph with nonnegative weights → Dijkstraweighted graph with negative weights → Bellman-ford, SPFAdirected acyclic graph → topological sorting용어 정의경로의 길이 : 경로가 지나는 간선의 가중치의 합정점 \(u\)에서 정점 \(v\)의 최단경로 : u에서 v로 가는 경로의 길이가 최소인 경로간선의 완화(edge relaxation) : 정점 \(u\)에서 \(v\)로의 간선에 대해 dist[\(v\)] > dist[\(u\)] + weight(\(u, v\)) 만족하면 dist[\(v\)]를..

그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까?사이클이 없는 무향 그래프(트리)에서 최장거리트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다.사이클이 없는 유향 그래프에서 최장거리일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자.동적 계획법정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자.$$ D[i] = \text{정점 } i \text{ 에서} v..

사이클(Cycle) 이란 그래프에서 사이클은 한 정점에서 시작하여 어떤 경로를 지나 다시 그 정점으로 돌아오는 경로를 말한다. 유향, 무향 그래프에서 사이클을 찾는 방법을 알아보자. 유향 그래프에서 사이클 찾기 유향 그래프에서 사이클은 DFS를 사용해 찾을 수 있다. DFS 수행 중 역행 간선이 있다면 그래프 내 사이클이 있다고 판별할 수 있다. #include using namespace std; int visited[10]; vector adj[10]; bool dfs(int here) { visited[here] = 1; for(int& there : adj[here]) { if(visited[there]) return true; if(dfs(there)) return true; } return f..