# 1753. 최단경로

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

 

문제 링크 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

문제 풀이

 

▶  문제 조건

• 정점의 개수 V (1 <= V <= 20,000)
• 간선의 개수 E (1 <= E <= 300,000)
• 간선 (u, v, w) (w: u→v로 가는 가중치 w인 간선), (u != v)
• 서로 다른 두 정점 사이 여러 개의 간선 존재 가능
• 모든 간선의 가중치 → 10 이하의 자연수

문제의 조건을 보면, 주어진 시작점에서 i번 정점까지의 최단거리를 구해야 함을 알 수 있다.

최단경로를 구하는 알고리즘에는 크게 3가지가 존재하는데,

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 플로이드-워셜 알고리즘

✔ 이 문제에서는 하나의 정점에서 모든 정점까지의 최단경로를 구해야 하고, 간선에 음의 가중치가 없기 때문에

다익스트라 알고리즘을 이용하여 해결해야 함을 알 수 있다.

 

✔ 다익스트라는 배열로 구하는 방법과, 우선순위 큐를 이용하는 방법 이렇게 2가지가 존재하는데,

배열로 구현 시 시간 복잡도가 O(V^2)이고, 우선순위 큐를 이용하면 시간 복잡도가 O(E+Vlog(V))로 배열에 비해

시간 단축 정도가 크기 때문에 우선순위 큐를 이용하여 시간 초과를 해결할 수 있다.

 

<다익스트라 알고리즘의 흐름>

1.  시작 노드와 직접적으로 연결된 모든 정점들의 거리 업데이트
2.  시작 노드를 방문한 노드로 체크
3.  시작 노드와 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점 선택
4.  해당 정점을 방문한 노드로 체크
5.  3번 과정에 의해 갱신될 수 있는 정점들의 거리 갱신
6.  위의 과정 반복

 

---

C++ 코드

 

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

#define endl "\n"
#define MAX 20010
#define INF 987654321

using namespace std;

int v, e, start; // 정점 v, 간선 e, 시작점 start
int d[MAX]; // 최소 비용 배열
vector<pair<int, int>> vertex[MAX]; // pair<간선, 비용> 

void input()
{
    cin >> v >> e >> start;

    for(int i = 0; i < e; i++)
    {
        int u, v, w; 
        cin >> u >> v >> w;
        vertex[u].push_back(make_pair(v, w));
    }
    for(int i = 1; i <= v; i++) d[i] = INF; // 배열 초기화
}

void dijkstra()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, start)); // pair<비용, 도착 노드>
    d[start] = 0; // 시작 노드에서 시작 노드로 가는 비용 0

    while(PQ.empty() == 0)
    {
        int cost = -PQ.top().first; 
        // 비용 값이 음수화 된 상태로(최소 비용부터 top에 옴) 정렬되어 있으므로 다시 양수화하여 사용
        int current = PQ.top().second;
        PQ.pop();

        for(int i = 0; i < vertex[current].size(); i++)
        {
            int next = vertex[current][i].first;
            int next_cost = vertex[current][i].second;

            if(d[next] > cost + next_cost) // 최소비용 갱신
            {
                d[next] = cost + next_cost;
                PQ.push(make_pair(-d[next], next));
            }
        }
    }

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

void solve()
{
    input();
    dijkstra();
}

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

    solve();

    return 0;
}