알고리즘 스터디
- 종만북) 30장 최단 경로 알고리즘 ~
- 백준 11657 타임머신 ~
- 백준 1865 웜홀 O
- 백준 11404 플로이드 O
- 백준 1613 역사 O
- 백준 2610 회의준비 O
- 동빈나 - 다익스트라 알고리즘
https://www.youtube.com/watch?v=611B-9zk2o4
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> dist;
//adj[curNode] = {{nextNode, w}, ...}
vector<vector<pair<int, int>>> adj;
void priority_queue_dijkstra(int start){
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
dist[start] = 0;
while (!pq.empty()){
int curW = -pq.top().first;
int curNode = pq.top().second;
pq.pop();
for (int i = 0; i < adj[curNode].size(); i++){
int nextNode = adj[curNode][i].first;
int nextW = adj[curNode][i].second;
if (dist[nextNode] > curW + nextW){
dist[nextNode] = curW + nextW;
pq.push({ -dist[nextNode], nextNode });
}
}
}
}
- 동빈나 - 벨만-포드 알고리즘
https://www.youtube.com/watch?v=Ppimbaxm8d8
#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 1000;
const int INF = 987654321;
//정점의 개수
int V;
//그래프의 인접 리스트 <연결된 정점 번호, 간선의 가중치>
vector<pair<int, int>> adj[MAX_V];
//음수 사이클이 있을 경우 텅 빈 배열 반환
//시작 정점 src
vector<int> bellmanFord(int src) {
//시작점을 제외한 모든 정점까지의 최단 거리 상한 INF
vector<int> upper(V, INF);
upper[src] = 0;
bool updated;
//V번 순회
for (int iter = 0; iter < V; ++iter) {
updated = false;
for (int here = 0; here < V; ++here) {
for (int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].first;
int cost = adj[here][i].second;
//(here, there)간선을 따라 완화 시도
if (upper[there] > upper[here] + cost) {
//성공
upper[there] = upper[here] + cost;
updated = true;
}
}
}
//모든 간선에 대해 완화가 실패했을 경우 V-1번 돌 필요 없이 곧장 종료
if (!updated) break;
}
//V번째 순회에도 완화가 성공했다면 음수 사이클 존재
if (updated) upper.clear();
return upper;
}
- 동빈나 - 플로이드 알고리즘
https://www.youtube.com/watch?v=9574GHxCbKc
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 500;
//정점의 개수
int V;
//그래프의 인접 행렬 표현
//adj[u][v] = u에서 v로 가는 간선의 가중치
int adj[MAX_V][MAX_V];
//플로이드-와샬 알고리즘
void floyd() {
for (int i = 0; i < V; ++i)
adj[i][i] = 0;
//i지점 -> j지점으로 이동할 때 거쳐가는 지점 K
for (int k = 0; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}