my devlog;

최단 경로 : 그래프에서 정점 u로부터 정점 v로 가는 경로 중에서 에지들의 가중치 합이 최소가 되는 경로. 혹은 에지의 개수가 가장 적은 경로. 다익스트라 알고리즘 (Dijkstra Algorithm) : 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾을 수 있는 알고리즘. ▷ 아이디어 : 방문하지 않은 정점 중에서 가장 비용이 적은 에지로 연결된 정점을 방문. 시작 정점으로부터 해당 정점을 경유지로 하여 다른 정점을 방문하는 비용이 더 작다면, 최단 경로값을 갱신. 위의 그림에서 distance[u]가 distance[w]값보다 작아서 가장 비용이 적은 에지로 연결된 정점 u가 새롭게 추가되었다면(방문되었다면), 시작 정점 v로부터 해당 정점 u를 거쳐서 다른 정점인 w로 가는 비용을 계산한다..

스패닝 트리 (Spanning Tree) -> 연결 그래프 G의 스패닝(신장) 트리란, G의 모든 정점을 포함하는 부분 그래프로서의 트리. 모든 정점들이 연결되어 있어야 하며 사이클이 존재해서는 안 됨. n개의 정점을 갖는 스패닝 트리는 반드시 n-1개의 에지를 가짐. 최소 스패닝 트리(최소 신장 트리) -> 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치 합이 최소인 스패닝 트리. ▷ Prim의 MST 알고리즘 ○ 아이디어 : 스패닝 트리 집합의 인접 정점 중 최소 가중치로 연결된 정점을 추가하며 스패닝 트리 집합을 점진적으로 확장해 나가자! ○ 알고리즘 1. 임의의 시작 정점에서 출발. (대개 인덱스가 가장 작은 정점) 시작 정점을 스패닝 트리 집합(MST)에 추가. 2. MST에 인접한 정점 ..

필수로 지나야 하는 정점이 두 개 주어지는 최단 경로 문제. 주의할 점: 필수 정점의 순서는 주어지지 않는다. v1을 먼저 가도 되고, v2를 먼저 가도 된다. #include #include #include #include #define MAX 805 #define INF 98765432 using namespace std; int N, E, v1, v2; vector graph[MAX]; int d[MAX]; void init() { for (int i = 1; i > N >> E; for (int i = 0; i > a >> b >> c; graph[a].push_back(make_pair(b, c)); graph[b].push_back(make..

Dijkstra 알고리즘을 활용해볼 수 있는 간단한 문제 주의할 점: 1. 가중치가 가장 작은 간선을 구할 때, 직접 비교하면 시간이 초과하므로 우선순위큐를 활용한다. 2. cin,cout은 scanf,printf보다 오래 걸린다. #include #include #include #define MAX 20010 #define INF 987654321 using namespace std; int V, E, start; vector a[MAX]; int d[MAX]; void dijkstra() { priority_queue pq; d[start] = 0; pq.push(make_pair(0, start)); while (pq.empty() == 0) { int current = pq.top().second..