[Algorithm] 다익스트라

다익스트라

그래프에서 한 정점에서 다른 모든 정점 까지의 최단 거리를 구할 수 있는 알고리즘이다.

시간복잡도는 ElogE or ElogV

자료구조

다익스트라 알고리즘에서 저장해야하는 정보는 다음과 같다.

• 노드별 최소 비용을 저장할 배열
• 간선의 노드 연결과 비용을 저장할  vector 배열
• 경로 탐색을 위해 prev 배열

여기서 adj에는 adj[시작노드] = {비용, 끝노드} 형태로 정보를 저장한다.

비용이 key인 이유는 비용을 기준으로 priority_queue에 넣기 위해서...!

int d[1005];
vector<pair<int, int>> adj[1005];
int pre[1005];

이때 최소 비용 배열 d는 INF 값으로 초기화 해줘야한다.

int INF = 0x3f3f3f3f;
fill(d, d+n+1, INF);

구현

다익스트라 알고리즘은 시작정점에서 부터 하나씩 최소 비용이 드는 노드를 선택해가면서 전체 최소비용을 구한다.

특정 노드까지 가는 비용과 노드를 저장할 수 있는 우선순위 큐를 선언한 다음

시작노드까지의 거리는 0, pq에 push한다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> pq;
d[st] = 0;
pq.push({d[st], st});

이 후 pq가 빌때까지 노드를 선택하고 최소비용 배열을 업데이트 하면 된다.

 최소비용 트리의 값과 pq의 비용이 다르다면 이미 더 작은 비용으로 경로가 연결된 것이므로 continue 처리를 한다.

update 후보군들을 cur 노드와 연결된 노드들이므로 adj에서 가져온다.

이때 d의 nxt까지의 비용과 cur까지의 비용 + cur에서 nxt의 비용을 비교해 더 갱신이 필요하면 해준다.

갱신시 d를 업데이트하고 pq에 nxt까지의 비용과 nxt를 push 해준다.

이때 경로복원을 위한 pre도 수정한다.

while(!pq.empty())
{
	auto cur = pq.top(); pq.pop();
    if(d[cur.Y] != cur.X) continue;
    for(auto nxt: adj[cur.Y]){
    	if(d[nxt.Y] <= d[cur.Y] + nxt.X) continue;
        d[nxt.Y] = d[cur.Y] + nxt.X;
        pq.push({d[nxt.Y], nxt.Y});
        pre[nxt.Y] = cur.Y;

경로 복원

경로 복원의 경우 prev[end]에서 부터 값이 start 노드가 나올때까지 타고 들어가면 된다.

vector<int> path;
cur = end;
while(cur != start){
	path.push_back(cur);
    cur = pre[cur];
}
path.push_back(cur);

reverse(path.begin(), path.end());
for(int node: path) cout << node << ' ';