[최단경로/다익스트라] 1238 파티

다익스트라 알고리즘은 one to all 최단경로 알고리즘이다. 다시말해서, 하나의 정점에서 시작해서 다른 모든 정점까지의 최단경로를 구하기 위해 사용하는 알고리즘이다.

다익스트라 알고리즘은 모든 엣지중 하나라도 음의 가중치를 가지면 제대로 동작하지 않는다.

배열 2가지를 사용하는데

1. 배열 d[i] => i번째 정점까지의 최단거리가 몇인지가 저장된다.

2. 배열 visited[i] => i번째 정점을 방문 했는지 안했는지 여부가 저장된다.

알고리즘의 동작 순서는 다음과 같다.

1. 배열 d[i]에 들어있는 값중 제일 작은값을 갖는 정점을 선택한다.

2. 그 정점에 연결 되어 있는 정점들 중에 아직 방문하지 않은 정점을 포함하는 엣지에 대해서

3. 릴렉스 연산을 한다.

릴렉스 연산이란, 두 정점 U,V가 있을때 그 U,V를 포함하는 엣지에 대해서

IF(d[u] > d[v] + w[v][u])

d[u] = d[v]+ w[v][u];

와 같이 최단 거리를 갱신해주는 연산을 말한다.

위의 문제에서 다익스트라 알고리즘을 사용해서 풀기 위해서는 약간의 변형이 필요하다.

첫번째.2번 정점에서 시작해서 다른 모든 정점까지 가는 최단 경로의 길이를 구해야한다.

두번째.다른 모든 정점들에서 2번정점까지 오는 모든 최단 경로의 길이를 구해야 한다.

왜냐면 각 마을에 있는 사람들이 파티가 열리는 곳까지 최단거리로 갔다가 최단거리로 돌아와야 하기 때문이다.

(그래프는 비방향 그래프이다.)

첫번째는 그냥 다익스트라 알고리즘을 사용하면 되는데 두번째는 어떻게 해야 될까?

이것도 마찬가지로 그냥 다익스트라 알고리즘을 사용하면 된다.

다만, 방향그래프의 방향을 뒤집어 준다음, 다익스트라 알고리즘을 돌려야 한다.

다른 모든 노드들중 하나(출발 노드)에서 시작해서 2번 정점까지 오는 최단 경로의 길이는

다시말하면, 모든 엣지의 방향을 뒤집은다음에 2번 정점에서 그 출발 노드까지 가는 최단 경로의 길이와 똑같을 것이다.

이것을 ALL-TO-ONE 최단거리 알고리즘이라고 한다.

다익스트라 알고리즘을 활용해서 구할수 있다.

유튜브에 아주 잘 설명해주시는 분이 있기 때문에 약 1시간 반정도 이 강의를 보고나서 이 글을 다시 보길 바란다. 그럼 이해가 완벽하게 될것이다.

https://www.youtube.com/watch?v=QH-Btq8SgLQ

https://www.youtube.com/watch?v=icqzGct4V1s

소스코드

#include <iostream>
#include <algorithm>
#include <memory.h>
#define INT_MAX 99999999;
#define INT_MIN -99999999;
using namespace std;
int n,m,start;
 
bool visited[1001];//점i를 이미 방문했는가
int d1[1001];//d[i]는 점i까지 오는데 최단거리를 저장함. -> one to all
int d2[1001]; //d2[i]는 반대로 다른 모든 노드들에서 정점i까지 오는 최단경로길이를 저장함. ->all to one
int w[1001][1001];//인접행렬
 
void dijkstra(int* d) {
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= n; i++)
        d[i] = INT_MAX;
    d[start] = 0;
    /*다익 스트라 동작 순서
    1.현재 정점 중에서 d값이 제일 작은 정점을 방문함.
    2.그 정점에 연결되고 아직 방문하지 않은 정점을 포함하는 엣지에 대해
    3.릴렉스 연산을 한다.
    */
    int cnt = 0;
    while(cnt != n) {
        int v; //아직 방문하지 않은점 중에서,d값이 최소인 정점의 인덱스가 저장됨.
        int MIN = INT_MAX;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && MIN > d[i]) {
                v = i;
                MIN = d[i];
            }
        }//1번 O(n)
        visited[v] = true;
        cnt++;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && w[v][i]) {
                if (d[i] > d[v] + w[v][i]) {
                    d[i] = d[v] + w[v][i];
                }
            }
        }//2,3번 O(n)
    }//O(n^2)
}
 
 
int main() {
    cin >> n >> m >> start;
    for (int i = 1; i <= m; i++) {
        int a, b,c;
        cin >> a >> b>>c;
        w[a][b] = c;
    } //엣지의 개수만큼 입력을 받음.
 
    dijkstra(d1);//O(n)
    //d배열에는 start정점에서 다른 모든 노드들까지 가는 최단경로의 cost가 저장되어 있음.
    //one-to-all 방식
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            int temp = w[i][j];
            w[i][j] = w[j][i];
            w[j][i] = temp;
        }
    }//엣지의 방향을 반대로 바꿔줌.
    //all-to-one방식 다른 모든 노드들에서 하나의 정점까지 오는 최단거리 cost를 구하기 위함.
    dijkstra(d2);
    int MAX = INT_MIN;
    for (int i = 1; i <= n; i++) {
        if (MAX< d1[i] + d2[i])
            MAX = d1[i] + d2[i];
    } 
    //시작점 start에서 i까지 가는 최단경로(d[i]) + i에서 start까지 오는 최단경로(d2[i])의 합중 최소를 구하자.
    cout << MAX << endl;
    return 0;
}