Dijkstra

//다익스트라의 최단 거리 알고리즘의 구현
 
//정점의 개수
int V;
//그래프의 인접 리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다.
vector<pair<int, int>> adj[MAX_V];
vector<int> dijkstra(int src)
{
    vector<int> dist(V, INF);
    dist[src] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, src));
    while(!pq.empty())
    {
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        //만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸 것을 무시한다.
        if(dist[here] < cost) continue;
        //인접한 정점들을 모두 검사한다.
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            //더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.
            if(int i = 0; i<adj[here].size(); ++i)
            {
                int there = adj[here][i].first;
                int nextDist = cost + adj[here][i].second;
                //더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.
                if(dist[there] > nextDist)
                {
                    dist[there] = nextDist;
                    pq.push(make_pair(-nextDist, there));
                }
            }
        }
    }
    return dist;
}

 

 

Dijkstra algorithm

단일 시작점 최단 경로 알고리즘

시작 정점에서부터 다른 정점까지들의 최단 거리를 계산합니다.

음수 싸이클이 있으면 사용불가!

 

시간복잡도

O(|E|lg|v|)

 

 

 

 

 

프로그래밍 대회에서 배우는 알고리즘 문제해결전략2