다익스트라 알고리즘

[접기]

목차

  • 1. 개요
  • 2. 알고리즘
  • 3. 소스 코드
  • 4. 추천 문제


1. 개요


가중치가 있는 방향 그래프에서 임의의 노드 하나와 다른 모든 점 사이의 거리를 구하는 알고리즘이다.

2. 알고리즘



3. 소스 코드



vector > adj[MAX_V];
int V;

vector dijkstra(int src) {
vector dist(V + 1, INF);
dist[src] = 0;
priority_queue > pq;
pq.push(make_pair(0, src));
while (!pq.empty()) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if (dist[here] < cost)
continue;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i].first;
int nextDist = cost + adj[here][i].second;
if (dist[there] > nextDist) {
dist[there] = nextDist;
pq.push(make_pair(-nextDist, there));
}
}
}
return dist;
}

4. 추천 문제




분류 알고리즘