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

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

• 다익스트라(Dijkstra) 알고리즘은 출발점이 있는 곳에서 모든 정점까지의 최단거리를 찾는 알고리즘이다.
• 경로에 음수가 포함되면 경로를 찾을 수 없다.
• 알고리즘
  1. 모든 정점의 최단거리를 구할 배열 d[]를 만들고 배열에 INF 값을 채워 넣는다.(INF 는 경로의 계산에서 나올 수 없는 매우 큰 값을 의미한다.)
  2. 출발하는 정점의 위치에 0을 채워 넣는다.
  3. 방문하지 않은 경로 중 현재까지의 값중에서 가장 짧은 거리의 정점을 선택한다.(만약 이 값이 INF 라면 갈 곳이 없다는 것이므로 더이상 진행하지 않아도 된다.)
  4. 선택된 정점은 방문한 정점으로 마킹을 한다.
  5. 선택된 정점에서 갈 수 있는 모든 경로를 가 보면서 자신까지 온 거리와 다음 정점까지 갈 수 있는 거리의 합이 다음 정점의 값이 출발점에서 온 값보다 작다면 갱신한다.
  6.  모든 정점을 방문할 때까지 3~5를 계속 수행한다.

문제 예

정올 2109:꿀꿀이 축제

X 마을에서 축제를 하기 때문에 모든 마을에서 X마을에 도착하는 거리와 X마을에서 다시 각각의 마을로 돌아가는 거리를 구해서 가장 많은 시간이 걸리는 꿀꿀이의 소요시간을 구하는 문제이다.

여기서 X마을에서 각각의 마을로 돌아가는 거리를 구하는 것은 다익스트라 알고리즘을 간단하게 해결이 가능하다.

하지만 각각의 마을에서 X마을로 오는 시간을 구하는 것은 쉽지 않다.

이때 방향을 거꾸로 생각한다면 어떨까? 가령 A->X 의 방향을 A<-X  형태로 바꾼 후 X마을에서 각각의 마을을 찾아가는 다익스트라 알고리즘으로 구할 수 있게 된다.

즉 알고리즘은 다음과 같다.

1. 2번 마을에서 N개의 마을로 가는 최단거리

원래 그래프를 이용하여 다음과 같이 다익스트라 알고리즘으로 최단 거리 찾기

2. N개의 마을에서 2번 마을로 오는 최단 거리

방향을 바꾼 다음 다익스트라 알고리즘을 이용하여 최단거리를 찾는다.

 

소스코드 예)

#include <bits/stdc++.h>
#define INF 0x0fffffff

using namespace std;

struct Road{
    int target,val;

    bool operator < (const struct Road &r)const{
        return val > r.val;
    }
};
void dijkstra(int n,int x,vector<struct Road> route[],vector<int> &d){
    priority_queue <struct Road> pq;

    for(int i=1;i<=n;i++) d[i]=INF;
    d[x]=0;
    pq.push({x,0}); /// 출발점을 pq에 넣는다.

    int cur,curVal;
    int next,nextVal;
    while(!pq.empty()){
        cur = pq.top().target;
        curVal = pq.top().val; ///현재까지 온 경로 거리
        pq.pop();

        for(int i=0;i<route[cur].size();i++){
            next = route[cur][i].target;
            nextVal = curVal + route[cur][i].val; ///다음 경로까지 가는 거리
            if(d[next]>nextVal){
                d[next]=nextVal;
                pq.push({next,nextVal});
            }
        }
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    int N,M,X;
    cin >> N >> M >> X;
    vector<struct Road>route[N+1],reverseRoute[N+1];
    vector<int> d(N+1),rd(N+1);
    int i,j,s,e,t;

    while(M--)
    {
        cin >> s >> e >> t;
        route[s].push_back({e,t});
        reverseRoute[e].push_back({s,t});
    }

    dijkstra(N,X,route,d);
    dijkstra(N,X,reverseRoute,rd);

    int ans=0;
    for(int i=1;i<=N;i++)
    {
        //cout << i << ":" << d[i] << "," << rd[i] <<"\n";
        ans=max(ans,d[i]+rd[i]);
    }

    cout << ans;
    return 0;
}