다익스트라 알고리즘 (Dijkstra)

다익스트라 알고리즘

하나의 정점에서 다른 정점들로의 최단경로 찾는 알고리즘

탐욕법과 다이나믹 프로그래밍 사용

 

우선순위 큐 (priority queue)을 통해 최소 비용 노드를 파악

→ 시간 복잡도 O(NlogN)

 

주의

모든 간선 가중치는 양의 정수여야 한다!(음수이면 안된다)

 

구현 요약

1. 시작 노드부터 시작

2. 현재 노드와 이어진 노드들중에 방문하지 않았고, 거리가 가장 짧은 노드를 선택한다

3. 연결된 노드로 이동하게 되면 드는 값과 기존값을 비교해서

더 비용이 작은 것을 선택한다.

 

구현

1) 시작!

dist는 0번노드에서 n번 노드까지의 거리를 저장할 배열이다.

 

시작 노드에서 시작노드까지의 값은 0이다. (자기 자신까지의 거리니까)

나머지는 아직 모르므로 다 무한값으로 초기화 한다.

 

 

2) 

시작 노드와 연결된 노드들을 살펴보자

노드 1,2번은 각각 1, 5만큼 떨어져 있다.

1,5는 무한값 보다 작으니 일단 표를 갱신하자

 

그 후 노드 1,2 중에 1이 비용이 저렴하므로

노드1을 방문하자.

 

3)

1번 노드와 연결된 노드들은 2,3,5이다.

 

노드 3, 노드5로 이동하는 값은 무한값보다 작으니 갱신해준다.

2번노드를 살펴보자 

노드0→노드2 로 이동하면 비용이 5가 들지만

노드0→노드1 → 노드2 로 이동하면 1+2=3만 든다.

3이 더 저렴하므로 갱신해준다.

 

 

노드 2,3,5에서 방문하지 않았고 가장 저렴한 비용은 2이므로

노드2를 방문하자

 

 

4)

노드 2를 방문한 후 위의 과정을 반복하자.

 

모두 방문하게 된다면 최종 결과를 얻을 수 있다.

0번노드에서 1,2,3,4,5번 노드로 이동하는 최소값은

0,1,3,4,4,2이다.

 

 

코드

priority queue를 사용해서 작성했다.

시간 복잡도 O(ElogV)

(V=노드 개수, E=간선 개수)

 

#include <vector>
#include <queue>
#include <limits>
#include <iostream>
using namespace std;

typedef pair<int, int> p; // distance, node

vector<int> dijkstra(vector<vector<p>>& graph, int start) 
{
    //Initiate///////////////////////
    vector<int> dist(graph.size(), numeric_limits<int>::max());//infinite number
    priority_queue<p, vector<p>, greater<p>> pq;//오름차순 정렬

    //First//////////////////////////
    dist[start] = 0;
    pq.push({ 0, start });

    //Check//////////////////////////
    while (!pq.empty()) 
    {
        int nowNode = pq.top().second;
        int nowDistance = pq.top().first;
        pq.pop();

        if (nowDistance > dist[nowNode]) continue;

        for (auto& edge : graph[nowNode]) 
        {
            int nextNode = edge.first;
            int weight = edge.second;

            if (dist[nowNode] + weight < dist[nextNode]) 
            {
                dist[nextNode] = dist[nowNode] + weight;
                pq.push({ dist[nextNode], nextNode });
            }
        }
    }

    return dist;
}

 

 

 

틀린게 있으면 알려주세요 

빠르게 수정하겠습니다~~