💡Dijkstra Algorithm
단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산
priority_queue <pair<int, int>> pq;
pq.push({ -nextDist, next });
// 거리를 음수 값으로 넣어주어 거리가 짧을 수록 우선 순위가 높게 정렬한다
int V;
//vertex number, weight
vector<pair<int, int>> adj[MAX];
vector<int> dijkstra(int src) {
vector<int> dist(V, INF);
dist[src] = 0;
priority_queue <pair<int, int>> pq;
pq.push({ 0, src }); // distance, vertex number
while (!pq.empty()) {
int cost = -pq.top().first;
int cur = pq.top().second;
pq.pop();
//지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 무시
if (dist[cur] < cost) continue;
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first; // vertex number adj with cur
int nextDist = cost + adj[cur][i].second;
//더 짧은 거리를 발견하면 dist[]갱신, 우선순위 큐에 넣음
if (dist[next] > nextDist) {
dist[next] = nextDist;
pq.push({ -nextDist, next });
}
}
}
return dist;
}
O(|E|)
, 이 경우 우선순위 큐에 원소를 추가하거나 삭제하는 데는 O(|lg|E||)
의 시간, 총 O(|E||lg|E||)
O(|V|^2+|E|)
의 시간 복잡도를 가짐vector<int> dijkstra2(int src) {
vector<int> dist(V, INF);
//각 정점을 방문했는지 여부 저장
vector<bool> visited(V, false);
dist[src] = 0; visited[src] = false;
while (true) {
int closest = INF, cur;
//아직 방문하지 않은 정점 중 가장 가까운 정점을 찾음
for (int i = 0; i < V; i++) {
if (dist[i] < closest && !visited[i]) {
cur = i;
closest = dist[i];
}
}
if (closest == INF) continue;
visited[cur] = true;
//가장 가까운 정점을 방문
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first;
if (visited[next]) continue;
int nextDist = dist[cur] + adj[cur][i].second;
dist[next] = min(dist[next], nextDist);
}
}
return dist;
}
이 문제는 다익스트라를 알면 바로 풀 수 있는 문제기 때문에 소스코드를 바로 첨부 (시간 초과 때문에 배열을 사용할 순 없고, 큐를 사용해도 아슬아슬하게 통과된다)
✏️Source Code
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int V_MAX = 20001;
const int INF = 1e8;
int V, E, K;
vector<pair<int, int>> adj[V_MAX]; //(vertex, weight)
vector<int> dist;
void input() {
cin >> V >> E >> K;
dist = vector<int>(V + 1, INF);
//input adj data
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({ v,w });
}
}
void dijkstra() {
priority_queue<pair<int, int>> pq; // weight, vertex
pq.push({ 0, K });
dist[K] = 0;
while (!pq.empty()) {
int cost = -pq.top().first;
int cur = pq.top().second;
pq.pop();
//already found shorter pathway
if (dist[cur] < cost) continue;
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first;
int nextDist = cost + adj[cur][i].second;
if (dist[next] > nextDist) {
dist[next] = nextDist;
pq.push({ -nextDist, next });
}
}
}
for (int i = 1; i <= V; i++) {
if (dist[i] == INF) cout << "INF" << endl;
else cout << dist[i] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
dijkstra();
return 0;
}