2JINISHAPPY 2JINISHAPPY

그래프 G 상에서 vertex u에서 v로의 가장 짧은 path의 길이를 찾는 문제를 최단경로 문제라고 한다. 최단 경로 문제는 주로 1️⃣ edge에 weight가 존재하는지 2️⃣ edge weight 범위가 0이상인지/정수인지 3️⃣ 특정 vertex u에서 도달 가능한 path만 구하는지/모든 vertex set에 대해 구하는지 에 따라 사용할 알고리즘을 정하게 된다. 그 중 Dijkstra Algorithm은 edge에 weight가 존재하면서, 범위가 0 이상 이고 특정 vertex u에서 도달 가능한 vertex들의path를 구할 때 사용하는 알고리즘이다. 위 그림과 같은 형태에서 vertex f -> d로의 path는 여러 형태가 존재할 수 있지만, shotest path는 f-b-a-c-..

#include #include #include #define INF 987654321 using namespace std; vector graph; int V, E; int prim() { vector cost(V + 1, INF); vector prev(V + 1, -1); vector visit(V + 1, false); priority_queue pq; pq.push(make_pair(0, 1)); cost[1] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); visit[u] = true; for (auto next : graph[u]) { int v = next.second; int weight = next.first; if (!vi..