[다익스트라]

이번엔 다익스트라 알고리즘에 대해서 설명해줄게.  다익스트라 알고리즘이란 모든 정점을 방문해서

시작점에서 도착점으로 가는 최단거리를 구할때 사용되는 알고리즘이야. 모든 정점을 방문하기 때문에 굳이 정렬을 할 필요가 없다는 것이 장점. check[i]배열을 둬서 true이면 통과하고 아니면 최단거리를 구하기 시작해. 최단거리를 구하는 방법은

1.체크되어있지 않은 정점 중에서 dist의 값이 가장 작은 정점 x를 선택하고,

2.x를 체크한뒤 

3. x와 연결된 모든 정점을 검사하기 시작해. 

즉 간선을 (start, end ,cost)라고 했을 때,

dist[end] > dist[start]+ cost라고 하면 dist[end]=dist[start]+cost로 갱신해주는 알고리즘이야! 굉장히 간단하지

비슷한 알고리즘으론 플로이드-워셜 알고리즘이 있는데 이 알고리즘은 복잡도가 3중 반복문이기 떄문에 잘 쓰이지 않아. 그래도 굉장히 단순하고 쉬운 알고리즘이므로 데이터가 적을떈 효과적일 수 있어.

모든 정점을 검사할 땐, 우선큐나 set를 이용하면 되는데 나같은 경우엔 set를 이용했어. 조금 느린 느낌?이 없잖아 있지만 일단 손에 익은게 set이라서 그렇고 우선큐도 중요하게 쓰이니 알아둘 필요가 있을것 같아.

처음부터 시작점이 정해져 있는 경우도 있지만 아닐 때도 있으니 구분해야될 필요가 있어.

다음코드는 최소비용구하기 2라는 문제인데 다익스트라관련 문제이니 잊지않게 종종볼것!

최소비용 구하기 2 성공스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	2512	1116	593	42.297%

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

예제 입력 1 

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1 

4
3
1 3 5

ㅇ코드ㅇ

#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
struct Edge {
    int to;
    int cost;
    Edge(int to, int cost) : to(to), cost(cost) {
    }
};
vector<Edge> a[1001];
int dist[1001];
bool check[1001];
int from[1001];
int inf = 1000000000;
int main() {
    int n;
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    for (int i=0; i<m; i++) {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        a[x].push_back(Edge(y,z));
    }
    int start, end;
    scanf("%d %d",&start,&end);
    for (int i=1; i<=n; i++) {
        dist[i] = inf;
    }
    dist[start] = 0;
    from[start] = -1;
    for (int k=0; k<n-1; k++) {
        int m = inf+1;
        int x = -1;
        for (int i=1; i<=n; i++) {
            if (check[i] == false && m > dist[i]) {
                m = dist[i];
                x = i;
            }
        }
        check[x] = true;
        for (int i=0; i<a[x].size(); i++) {
            int y = a[x][i].to;
            if (dist[y] > dist[x] + a[x][i].cost) {
                dist[y] = dist[x] + a[x][i].cost;
                from[y] = x;
            }
        }
    }
    printf("%d\n",dist[end]);
    stack<int> st;
    int x = end;
    while (x != -1) {
        st.push(x);
        x = from[x];
    }
    printf("%d\n",st.size());
    while (!st.empty()) {
        printf("%d ",st.top());
        st.pop();
    }
    printf("\n");
    return 0;
}