Dijkstra 알고리즘

가중치가 있는 방향 그래프에서, 한 정점으로부터 다른 정점까지의 최단 거리를 구하는 알고리즘

먼저 dist를 무한대로 초기화

dist[i]는 1번 정점에서 i번 정점까지의 최소 비용을 저장한다.

1번 정점에서 출발하므로 dist[1]은 0으로 초기화한다.

 

1번 정점에서 2번 또는 3번으로 갈 수 있다.

1에서 2로 가는 간선의 가중치가 12이므로, 0에 12를 더한다.

기존 값보다 작으면 갱신해준다. 처음에는 무한대니까 갱신된다.

1에서 3으로 갈때는 간선이 4니까 0에 4를 더해 dist[3]을 4로 갱신한다.

 

그렇게 해서 다 바꿨다 하면 다시 최소값을 찾는다. (이때 체크한 것은 제외)

이번에는 3이 체크되면서 최소값이 된다.

1번에서 3번으로 가는 비용은 4라는 것이다.

 

★ 이 최소값 4는 앞으로 다른 경로에 의해 갱신될 일이 없다.
다른 정점을 통해 3번 정점으로 오더라도 4보다 작아질 수 없는데,

이는 다익스트라 알고리즘이 간선 가중치가 양수일 때만 적용되기 때문이다.
따라서 3번 정점의 최단 거리는 4로 확정되고, 이를 체크한다.

 

이후 3번 정점에서 퍼져나가는데, 연결된 정점은 4번 정점뿐이다.
그래서 1→3의 거리 4에 가중치 5를 더해, 4번 정점의 거리를 9로 갱신한다.

 

이제 다시 체크된거 제외하고 최소를 찾는다. 이번에는 정점 4의 값 9가 선택된다.
이때 4번 정점에서 2번 정점으로 가는 간선의 가중치는 2이다.
1→4의 거리 9에 2를 더해 11이 되고, 기존 값 12보다 작으므로 11로 갱신한다.
또한 4번 정점에서 5번 정점으로 가는 간선이 있으므로, 9에 5를 더해 dist[5]를 갱신한다.

또 다시 체크 제외한것중 최소를 찾으면 2가 된다.

2→5는 11+5인데 이것은 14보다 크므로 그냥 pass.

그다음으로 최소값을 찾으면 14가 선택된다.
5번 정점에서 갈 수 있는 정점은 없으므로 그냥 끝낸다. 
그리고 마지막으로 6번 정점은 (초기값이 무한대라면) 선택되지 않도록 코드를 작성한다.

 

★ 하지만 이렇게 하면 1차원 배열에서 매 루틴마다 모든 정점을 돌며 최소값을 찾아야 한다.
그래서 우선순위 큐를 사용해 (2, 12), (3, 4)와 같은 형태로 값을 넣는다.
이렇게 하면 매번 n번을 도는 것이 아닌, log n번만에 최소값을 찾을 수 있다.
정점이 10만 개라면 배열 방식은 최소값을 찾기 위해 매번 10만 번을 순회해야 한다.
반면 우선순위 큐를 사용하면 이진 트리 구조이므로 약 log n, 즉 17번 정도의 연산만으로 가장 작은 값을 찾을 수 있다.

 

코드

cin>>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;
	Q.pop();
	if(cost>dist[now]) continue;
	for(i=0; i<graph[now].size(); i++){
		int next-graph[now][i].first;
		int nextDis=cost+graph[now][i].second;
		if(dist[next]>nextDis){
			dis[next]=nextDis;
			Q.push(Edge(next, nextDis));
		}
	}
}

 

 

 

 

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)