[개념] 최단 경로 구하기

가장 빠르게 도달 하는 방법

그리디 알고리즘 및 다이나믹 알고리즘의 한 유형

가장 짧은 경로를 찾는 알고리즘

예 )

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

종류

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

---

다익스트라 최단 경로 알고리즘

각 노드에서 현재까지의 최단거리 정보를 항상 1 차원 리스트에 저장하며 리스트를 계속 갱신

• 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로 구해주는 알고리즘
• 음의 간선이 없을 때 사용 가능
• **가장 비용이 적은 노드**를 선택해 임의의 과정 반복
• 원리
  1. 출발 노드를 정함
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 위 과정에서 3,4 반복

다익스트라 알고리즘 구현방법

1. 구현하기 쉽지만 느림
2. 구현하기 조금 까다롭지만 빠름

1.
시간 복잡도 - O(V^2)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 10001
#define INF 1e9 

using namespace std;

int N, cnt, start;
vector<pair<int, int>> v[MAX];
bool visit[MAX];
int ans[MAX];
int findSmallN() {
    int tmpN = INF; // 가장 작은 수
    int index; // 가장 작은 수 index
    for (int i = 1; i <= N; i++) {
        if (ans[i] < tmpN && !visit[i]) {
            tmpN = ans[i];
            index = i;
        }
    }
    return index;
}
void func(int n) {
    visit[n] = true;
    // 배열 초기화
    for (int i = 0; i < v[n].size(); i++) {
        ans[v[n][i].first] = v[n][i].second;
    }
    // 노드들 중에서 가장 작은수 선택
    int smallN = findSmallN();

    for (int i = 0; i < N - 1; i++) {
        visit[smallN] = true;
        for (int j = 0; j < v[smallN].size(); j++) {
            ans[v[smallN][j].first] = min(ans[v[smallN][j].first], ans[smallN] + v[smallN][j].second);
        }
        smallN = findSmallN();
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    // 배열 가장 큰수로 초기화
    fill_n(ans, MAX, INF);

    cin >> N >> cnt >> start;
    ans[start] = 0;

    for (int i = 0; i < cnt; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
    }

    func(start);
    for (int i = 1; i <= N; i++) {
        cout << ans[i]<<"\n;
    }

}

2.

시간복잡도 - O(ElogV)

(E - 간선 갯수, V - 노드 갯수)

힙 자료구조 이용

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}

cf ) 힙이란?

• 우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제

• 데이터를 우선순위에 따라 처리하고 싶을 때 사용

• 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선시함 (최소힙)

최소 힙을 최대 힙 처럼 사용하기
일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 음수 부호(-) 를 붙여서 원래의 값으로 돌려놓는 방식

• C++ 최소힙/ 최대힙

    priority_queue<int, vector<int>, greater<int>> q; // 최소힙
    priority_queue<int, vector<int>> q;   // 최대힙

자료구조 

---

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

다익스트라 알고리즘과 비교하면 구현 과정에서 어려움을 겪지 않을 것이지만핵심아이디어가 중요하다

시간 복잡도 - O(N^3)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > v[100001];
// 최단 거리 테이블 만들기
int ans[100001];

void func(int n) {
    priority_queue < pair<int, int>, vector<pair<int,int>>> pq;
    pq.push({ 0,n });
    ans[n] = 0;
    while (!pq.empty()) {
        int node = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if (ans[now] < node) continue; //이미 연결한 적이 있는경우
        for (int j = 0; j < v[now].size(); j++) {
            int tmp = node + v[now][j].second;
            if (tmp < ans[v[now][j].first]) {
                ans[v[now][j].first] = tmp;
                pq.push({ tmp, v[now][j].first });
            }
        }

    }
}
int main(void) {
    cin >> n >> m;
    cin >> start;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });

    }
    fill(ans, ans+ 100001, INF);

    func(start);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == MAX) { cout << "INF" << "\n"; }
        else { cout << ans[i] << "\n"; }
    }
}