다락방

1504 특정한 최단 경로 #include using namespace std; int INF = 98765432; vector vec[802]; int dist[803]; void bfs(int a) { memset(dist, INF, sizeof(dist)); priority_queue queue; queue.push(make_pair(0, a)); dist[a] = 0; while (!queue.empty()) { int sum_distance = queue.top().first; int x = queue.top().second; queue.pop(); if (dist[x] < sum_distance) continue; for (int i = 0; i ncost) { queue.push({ ncos..

다익스트라 그래프의 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점뿐만 아니라 모든 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 동작과정 출발노드와 도착노드를 설정한다 ‘최단 거리 테이블’을 초기화 한다. 현재 위치한 노드의 인접노드 중 방문하지않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 짧은 노드를 선택한다. 그 노드를 방문처리한다. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)를 계산해 ‘최단 거리 테이블’ 을 업데이트 한다. 3-4 과정을 반복한다. ‘최단거리 테이블’ 은 1차원 배열로, N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개..