BOJ - 1753 최단 경로

1753번 최단경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 것이다.

특정 정점에서 갈 수 있는 모든 정점 까지의 최단 경로를 구하기 위해서는
다익스트라 알고리즘을 활용하면 된다.

다익스트라 알고리즘의 동작 방식은 다음과 같다.

1. 특정 정점에서 자기 자신까지의 거리는 0으로, 나머지 정점 까지의 거리는 굉장히 큰 수로 정해 준다.
2. 인접한 정점들을 탐색하며 거리를 최신화 해 준다.
3. 인접한 정점들과의 거리가 가장 작은 것을 선택한다.
4. 선택한 정점을 통해 다른 정점으로 가는 것을 고려하여 최소 거리를 갱신해 준다.
5. 위 과정을 반복한다.

위의 방식을 통해 특정 정점에서 모든 정점 까지의 최단 경로를 구할 수 있다.

다익스트라 알고리즘을 구현하기 위해 우선순위 큐(priority queue)를 사용하면 쉽게 구현할 수 있다.

모든 경로에 대하여 거리가 가장 작은것을 선택해야 하는데, 이 과정을 계속 진행하는 것보다 우선순위 큐를 활용하여 정렬을 해 두면 탐색에 필요한 시간을 줄일 수 있기 때문에 우선순위 큐를 활용한다.

아래의 코드는
현재 정점까지의 거리 + 현재 정점 부터 다음 정점까지의 거리 와
지금까지 구해 진 다음 정점까지의 거리를 비교하여 만약 전자가 더 작다면 새롭게 거리를 갱신해 주는 것이다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int,int>> V[20001];
int v,e,s;
int d[20001];

priority_queue<pair<int,int>> pq;

void di()
{
    for(int i=1;i<=v;i++)
        d[i] = 1000000000;

    d[s] = 0;

    pq.push(make_pair(0,s));
    while(!pq.empty())
    {
        int weight = -1*pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if(d[current] < weight) // 이미 갱신 된 경우
            continue;

        for(int i=0;i<V[current].size();i++)
        {
            int next = V[current][i].first;
	
    /** (다음 정점 까지 이미 구한 거리)와 (현재 정점까지의 거리 + 현재 정점부터 다음 정점 까지의 거리) 비교 **/
            if(d[next] > weight + V[current][i].second)
            {
                d[next] = weight + V[current][i].second;
                pq.push(make_pair(-d[next],next));
            }
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> v >> e;
    cin >> s;

    int a,b,c;
    for(int i=0;i<e;i++)
    {
        cin >> a >> b >> c;
        V[a].push_back(make_pair(b,c));
    }

    di();

    for(int i=1;i<=v;i++)
    {
        if(d[i] == 1000000000)
            cout << "INF" << "\n";
        else
            cout << d[i] << "\n";
    }

    return 0;
}

출처 : https://www.acmicpc.net/problem/1753