다익스트라 알고리즘

• 그래프 내, 시작 정점에서 목표 정점까지의 최단경로를 구해주는 알고리즘
• O((V+E)logE)
• 가중치가 음수인 간선이 존재할 때는 사용할 수 없다.

우선순위 큐

• 다익스트라를 사용하기 위해서는 우선순위 큐를 알아야 한다.
• 들어간 순서에 상관없이 우리가 정한 우선순위가 높은 원소를 추출한다.
• 힙구조를 이용한다.

힙이라는 자료구조를 이용하면 우선순위 큐의 삽입과 삭제를 O(logN)에 가능하다.
힙은 완전 이진 트리이다.

c++ : priority_queue

O(logN)번의 연산 안에 삽입 삭제가 가능
일반적 큐와 마찬가지로 top,size,pop,empty등의 함수가 내장되어 있다.

pq의 구현 방법

//그냥 일반전인 pq
#include <queue>
//새로운 비교연산자 만들고 싶을 때
#include <functional>
//기본적 pq는 큰 수 부터 나옴
priority_queue<ll> pq1;
//작은 수 부터 나오게 하는 방법
priority_queue<ll, vector<ll>, greater<>> pq2;
첫번째는 어떤자료형, 두번쨰는 구현체 즉 pq가 담길 공간, 세번째는 비교함수이다.

struct cmp{
	bool operator()(ll x,ll y) {return abs(x-3) > abs(y-3);}
};
priority_queue<ll, vector<ll>, cmp> pq3;

struct D{
	int a,b,c;
};

struct cmpD{
	bool operator() (D x,D y){
		if(x.a<y.a) return true;
        return true;
	}
};
priority_queue<D,vector<D>greater<cmpD>> pq4;

문제

11286 절댓값 힙

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m,s;
vector<int> a[200001];

struct cmp {
	bool operator()(ll a,ll b) {
		if (abs(a) == abs(b)) return a > b;
		return abs(a) > abs(b);
	}
};

int main() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;

	priority_queue < ll, vector < ll>, cmp> pq;

	while (t--) {
		ll c;
		cin >> c;
		if (!c) {
			if (pq.empty()) cout << "0" << '\n';
			else {
				cout << pq.top() << '\n';
				pq.pop();
			}
		}
		else {
			pq.push(c);
		}
	}
}

다익스트라 알고리즘

• 아직 방문하지 않은 정점들 중 시작점으로부터 거리가 가장 짧은 정점 u를 방문한다.
• 해당 정점 u와 인접하고 아직 미방문 상태인 정점들의 거리를 갱신한다.

위와 같이 거리를 저장할 배열을 저장해 놓는다. 출발지를 제외하고는 모두 무한대로 초기화 해놓는다.

그리고 각 이어진 노드별로 최소 이동 거리만 선택한다.

시간복잡도 O((V+E)logE)

문제

1753 최단경로