Shortest Path Problem

가중치 그래프(Weighted Graph)에서 한 정점에서 다른 정점으로 갈때, 가중치 합이 최소가 되도록 하는 경로를 찾는 알고리즘

최단 경로 문제의 종류

1. 단일 출발(single-source) 최단 경로
   : 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제
   

2. 단일 도착(single-destination) 최단 경로
   : 모든 점점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제
   (그래프 내의 간선들을 뒤집으면 단일 출발 최단 경로 경로 문제로 변경 가능)

3. 단일 쌍(single-pair) 최단 경로
   : 어떤 정점 v1에서 v2로 가는 최단 경로를 구하는 문제

4. 전체 쌍(all-pair) 최단 경로
   : 모든 정점 쌍들 사이의 최단 경로를 찾는 문제

1. Dijkstra Algorithm

V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘

• 각 정점을 최대 한번씩만 방문하여 최단 거리를 확정
• 아직 방문하지 않은 정점들 중 최단거리인 점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식으로 진행
• 총 V*V번 연산, 시간 복잡도 : O(V^2)
• 방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 혹은 힙 자료구조를 이용하면 알고리즘 개선 가능 : O(EloE)

알고리즘

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

풀어보면 좋은 문제

백준 5972번: 택배배송

#include<iostream>
#include<vector>
#include<queue>
#define MAX 50001
#define INF 987654321
using namespace std;

struct Data{int end, cost;};

int N, M;
int cost[MAX];
bool visit[MAX];
vector<Data> road[MAX];

void dijkstra(){
    priority_queue<pair<int, int> > pq;
    pq.push({0, 1}); // 시작점 : 1 
    while (!pq.empty()){
        int now_cost = pq.top().first;
        int now_node = pq.top().second;
        pq.pop();
        if(visit[now_node]) continue; // 방문한 경우 재 방문 x 
        visit[now_node] = true;
        for(int i=0; i<road[now_node].size(); i++){
            int next_node = road[now_node][i].end;
            int next_cost = road[now_node][i].cost;
            int before_cost = cost[next_node];
            int new_cost = cost[now_node]+next_cost;
            if(new_cost < before_cost){ // 더 적은 비용이 드는 경우 Update!!
                cost[next_node] = new_cost;
                pq.push({-new_cost, next_node});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    int a, b, c;
    for(int i=0; i<M; i++){
        cin >> a >> b >> c;
        road[a].push_back({b,c});
        road[b].push_back({a,c}); // 길이 양방향
    }
    for(int i=2; i<=N; i++) cost[i] = INF; // 초기화 
    cost[1] = 0; // 시작점 : 1 
    dijkstra(); // 다익스트라 
    cout << cost[N]; // 최소값 출력
}

2. Bellman-Ford Algorithm

V개의 정점과 E개의 간선을 가진 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘. 다익스트라 알고리즘과 달리 가중치가 음수인 경우에도 사용할 수 있음.

• 음의 사이클 존재 여부를 확인 가능
• 최단 거리를 구하기 위해 V-1번 E개의 모든 간선 확인 (음의 사이클 존재 여부 확인을 위해 한 번 더 E개의 간선을 확인)
• V번째 모든 간선을 확인하였을 때 거리배열이 업데이트 되는 경우, 음의 사이클을 가진 그리프
• 총 연산 횟수 : VxE = 시간 복잡도 O(VE)

알고리즘

1. 시작 정점을 선택한다.
2. 시작 정점에서 다른 노드들의 거리 값을 무한대로 설정하고 시작 노드는 0으로 설정한다.
3. 모든 간선들을 탐색하며 간선이 잇는 정점이 '한번이라도 계산 된 정점'이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트 한다. 이 과정을 V-1번 반복한다.
4. 마지막으로 음의 사이클 여부를 확인하기위해 3번을 한번 더 수행한다.

풀어보면 좋은 문제

백준 1865번: 웜홀

#include <iostream>
#include <vector>
#define INF 2100000000
#define MAX 501
using namespace std;

struct DATA{int start, end, cost;};
vector<DATA> G;

int TC, N, M, W, s, e, t;
int dist[MAX];

void init(){ // 초기화
    for(int i=1; i<=N; i++) dist[i] = INF;
    G.clear();
}

void bellmanFord(){
    dist[1] = 0;
    for(int i=1; i<=N; i++){
        for(int j=0; j<G.size(); j++){
            int start = G[j].start;
            int end = G[j].end;
            int cost = G[j].cost;
            // if(dist[start]==INF) continue;
            if(dist[start]+cost < dist[end]) {
                if(i==N) {
                    cout << "YES\n"; 
                    return ; 
                }
                dist[end] = dist[start]+cost;
            }
        }
    }
    cout << "NO\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> TC;
    while (TC--){
        cin >> N >> M >> W;
        init();
        while(M--){ // 도로 정보
            cin >> s >> e >> t;
            G.push_back({s, e, t});
            G.push_back({e, s, t}); // 도로는 방향이 없으며
        }
        while(W--){ // 웜홀 정보
            cin >> s >> e >> t;
            G.push_back({s, e, -t}); // 웜홀은 방향이 존재
        }
        bellmanFord();
    }
}

3. Floyd-Warshall Algorithm

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 모든 정점 사이의 최단경로를 구하는 알고리즘.

• 순환만 없다면 음수 가중치도 가능
• 동적계획법에 기반 - 어떤 두 정점 사이의 최단 경로는 어떤 경유지(K)를 거치거나 거치지 않는 경로 중 하나임. 즉, 정점 A와 정점 B 사이의 최단 경로는 A-B 이거나 A-K-B임. 경유지 K를 거친다면, 최단 경로를 이루는 부분 경로 역시 최단 경로임. (ex) A-K-B가 최단 경로라면, A-K 와 K-B도 최단 경로!)
• 시간 복잡도: O(V^3) (모든 가능한 경유지에 대해서 모든 정점에서 모든 정점으로 가는 최단거리를 확인)

알고리즘

시작점은 i, 끝점을 j, 경유점을 k라고 했을때 구하는 식은 다음과 같다.

adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

풀어보면 좋은 문제

백준 11404번: 플로이드

#include <iostream>
using namespace std;

int cost[101][101]={};
const int INF = 999999999;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, m; cin >> n >> m;
    int i, j, c;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(i==j) cost[i][j]=0;
            else cost[i][j]=INF;
        }
    }
    for(int k=0; k<m; k++){
        cin >> i >> j >> c;
        cost[i][j] = min(cost[i][j], c);
    }
    for(int k=1; k<=n; k++){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++)
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
        }
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++) {
            if(cost[i][j]==INF) cout << 0 << ' ';
            else cout << cost[i][j] << ' ';
        }
        cout << '\n';
    }
}