#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Edge{
int vex;
int dis;
Edge(int a, int b){
vex = a;
dis = b;
}
bool operator<(const Edge &ref)const{
return dis > ref.dis;
}
};
int main() {
priority_queue<Edge> pQ;
vector<pair<int,int>> graph[30];//인접리스트 그래프 그리기
int i, n, m, a, b, c;
cint >>n>>m;
vector<int> dist(n+1, 2147000000);//벡터 초기화
for(i = 1; i <= m; i++){
cin >> a >> b >> c;
graph[a].push_back(make_pair(b, c));
}
Q.push(Edge(1,0));
dist[1] = 0; //거리 넣음
while(!Q.empty()){
int now=Q.top().vex;
int cost=Q.top().dis; //훑었을때 dis가 가장 작은 값에서부터 시작
Q.pop();
if(cost > dist[now]) continue;
//dis[now]에는 원래 있던 값, cost에는 새로 들어온 값
//원래 있던 값이 더 작으면 걍 넘어가
for(i = 0; i<graph[now].size(); i++){
int next = graph[now][i].first; //연결된 노드번호
int nextDis = cost+graph[now][i].second//연결된 노드와의 cost누적
if(nextDis < dist[next]){ //원래 들어있던 값보다 누적값이 더 작으면
dist[next] = nextDis; //바꿔주기
Q.push(Edge(next,nextDis)); //새롭게 푸쉬하기
}
}
}
for(i = 2; i <= n; i++){
if(dist[i] != 2147000000) cout << i< << " : " << dist[i] << endl;
else cout << i << " : impossible" << endl;
}
return 0;
}
다익스트라 알고리즘은 프림,크루스칼 MST와 동일하게 Greedy하게 동작한다.
즉, 현재 나의 선택이 최선의 선택이라고 가정하고 찾아나가는 것이다.
따라서, 최소비용을 찾는다면 현재 노드로부터 연결된 간선중 작은 값을 선택하고 그 값이 최선이길 바라게 될 것이다.(그래서 정렬하거나 Priority queue를 활용)
다익스트라는 결국 BFS처럼 최단거리를 구하는 문제이지만, Greedy가 적용됨으로써 DP와 같이 복잡한 문제(노드가 많아지거나 규칙이 복잡한)를 보다 쉽게 해결하기 때문에 더 효율적일 수 있다.
하지만, 다익스트라는 간선의 가중치가 무조건 양수여야한다는 것이 중요하다.
Greedy하지는 않지만 다익스트라처럼 시작노드로부터 모든노드까지의 최단거리를 구하는 벨만포드 알고리즘은 음수도 처리가능하지만, 더 느리다.
다익스트라는 전반적으로 프림 알고리즘처럼 Greedy를인접리스트로 그래프 그리고 priority queue를 적용하여 풀어나가는 방식이다. 하지만, 쓰이는 활용도가 다르기 때문에 다익스트라는 거리값을 무한대로 초기화해놓고 최적의 값을 할당시키며 진행한다.
distance 배열을 할당하 되, 전부 무한대로 할당해 놓는다.(다익스트라&벨만포드 고유의 방법)
인덱스는 노드 번호를 뜻하며, 그 값은 시작 노드로부터 해당 노드(인덱스 번호)까지의 최단 거리를 의미한다.
무한대로 할당해놓는 이유는, 기존 값보다 작은 값이 할당되어야하기 때문에 가장 큰수 2147000000으로 초기화한다.
vector<int> dist(n+1, 2147000000);//벡터 초기화
인접리스트로 그래프를 완성한다.(Prim과 동일)
vector<pair<int,int>> graph[30];//인접리스트 그래프 그리기
for(i = 1; i <= m; i++){
cin >> a >> b >> c;
graph[a].push_back(make_pair(b, c));
}
현재 노드로부터 가중치가 가장 작은 값을 선택(Greedy)할건데, 매번 for문 돌리면 비효율적이므로 priority queue사용(Prim과 동일)
struct Edge{
int vex;
int dis;
Edge(int a, int b){
vex = a;
dis = b;
}
bool operator<(const Edge &ref)const{
return dis > ref.dis;
}
};
int main(){
priority_queue<Edge> pQ;
Q.push(Edge(1,0));//1번 노드에서 시작(문제에서 주어짐)
dist[1] = 0; //1번 노드에서 1번 노드는 당연히 거리가 0
}
priority queue를 이용했으니 top()으로 노드와 간선을 뽑아온다. 처음엔 1번 node(now)가 뽑힐 것이고 dis(cost)는 0이다. 기존의 dist[1]은 무한대였으므로 값을 0으로 relax(갱신)시켜준다. 그 다음 인접리스트를 훑어보며 연결된 노드를 찾아나간다.
1번 노드와 연결된 간선은 2번과 3번이다. 두 값은 모두 무한대였으므로 새로운 값으로 할당시켜준다. 그리고 priority queue에는 값이 dist기준으로 정렬된 상태로 push된다.
while(!Q.empty()){
int now=Q.top().vex;
int cost=Q.top().dis; //훑었을때 dis가 가장 작은 값에서부터 시작
Q.pop();//보통 값 넣고 바로 pop하네
if(cost > dist[now]) continue;
//dis[now]에는 원래 있던 값, cost에는 새로 들어온 값
//원래 있던 값이 더 작으면 걍 넘어가
for(i = 0; i<graph[now].size(); i++){
int next = graph[now][i].first; //연결된 노드번호
int nextDis = cost+graph[now][i].second//연결된 노드와의 cost누적
if(nextDis < dist[next]){ //원래 들어있던 값보다 누적값이 더 작으면
dist[next] = nextDis; //바꿔주기
Q.push(Edge(next,nextDis)); //새롭게 푸쉬하기
}
}
}
위에서 top이 node 3을 가리키고 있으므로 이제 node 3에서 시작한다. node 3은 오직 node 4하고만 연결되어 있으며, cost는 누적된 값인 9가 relax된다. 이제 top은 3을 가리킨다.
위에서 top이 node 4를 가리키고 있으므로 이제 node 4에서 시작한다. node 4는 node 2와 node 5와 연결되어 있다. 기존의 node2의 값인 12보다 11이 더 작으므로 값을 새롭게 갱신하고 node 5도 14로 갱신한다. 이제 top은 4을 가리킨다.
위에서 top이 node 2를 가리키고 있으므로 이제 node 2에서 시작한다. node2는 node 5하고만 연결되어 있다. 그런데 node 5의 기존 값은 14였으므로 고려하지 않고 continue한다. 이제 top은 2을 가리킨다.
위에서 top이 node2를 가리키고 있는데, 기존의 node 2는 값이 11이므로 고려하지않고 continue한다.
위에서 top이 node5를 가리키고 있는데, continue되지는 않지만 인접리스트 상 이어져있는 노드가 없어서 그냥 종료된다.
모든 pirority queue가 끝났으므로 종료되어 출력한다. 6은 impossible하다.
