[그래프]Dijikstra와 path tracking

Dijikstra

음수 가중치가 존재하지 않는 그래프에서 출발점에서부터 다른 도착점간의 최단 거리를 알아낼 때 사용되는 알고리즘

시간복잡도

O((v + e)log(e))

예시 코드

#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define INF 0x7fffffff

#define MAX_SIZE 20000

// 그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치) 쌍을 담아야 한다.
vector<pii> adj[MAX_SIZE]; 
int dist[MAX_SIZE];

void dijkstra(int src)
{
    // V만큼 배열을 INT_MAX로 초기화
    for(int i = 0; i < MAX_SIZE; i++)	dist[i] = INF;
    dist[src] = 0; // 시작점은 0으로 초기화 한다. 
 
    priority_queue<pii, vector<pii>, greater<pii> > 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 (pii next : adj[here])
        {
            int there = next.second;
            int nextDist = cost + next.first;
 
            // 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.
            // dist 벡터에는 시작점 -> there 위치까지의 최단 거리가 담겨있다.
            if (dist[there] > nextDist)
            {
                dist[there] = nextDist;
                pq.push(make_pair(nextDist, there));
            }
        }
    }
}
 

Path tracking

기존의 다익스트라 알고리즘은 한 출발점에서 다른 도착점들로 가는 최단 거리 값만을 구하는 알고리즘이다.
추적 배열을 사용하면 그 경로도 함께 구할 수 있다.

예시 코드

#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define INF 0x7fffffff

#define MAX_SIZE 20000

vector<pii> adj[MAX_SIZE]; 
int dist[MAX_SIZE];
int path[MAX_SIZE];

void dijkstra(int src)
{
    for(int i = 0; i < MAX_SIZE; i++)	dist[i] = INF;
    for(int i = 0; i < MAX_SIZE; i++)   path[i] = -1;
    dist[src] = 0; // 시작점은 0으로 초기화 한다. 
 
    priority_queue<pii, vector<pii>, greater<pii> > 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 (pii next : adj[here])
        {
            int there = next.second;
            int nextDist = cost + next.first;
 
            if (dist[there] > nextDist)
            {
                dist[there] = nextDist;
                path[there] = here; //*경로 역추적 배열 추가*
                pq.push(make_pair(nextDist, there));
            }
        }
    }
}

void pathTracking(int end_node){
    vector<int> stack;
    //역추적
    while(true){
        stack.push_back(end_node);
        end_node = path[end_node];
        if(end_node == -1)  break;
    }
    while(!stack.empty()){
        cout << stack.back() << (stack.size() == 1 ? "" : " -> ");
        stack.pop_back();
    }
    cout << endl;
}