[알고리즘] 최단 경로 ver.1

최단 경로 알고리즘

➡️ node와 가중치가 존재하고, 최저/최소값을 구하라고 하면 최단 경로를 의심해야 한다. 최단 경로 알고리즘은 다양하게 있는데, 각 알고리즘마다 사용하는 경우가 다르다.
(V: vertex==node, E: edge)

0. 경로 저장 방법.

// v는 vector<int> 형의 배열이다. ...는 node의 개수.
vector<int> v[...];
// arr은 문제에서 주는 경로 정보가 담긴 배열
for(int i=0; i<arr.size(); i++){
	v[node1].push_back(mp(node2, 가중치));
    // 양방향이면 아래 코드를 써주면 된다.
    v[node2].push_back(mp(node1, 가중치));
}

---

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

• 양수 가중치
• 특정 시작점이 있을 때, 그 시작점으로부터 다른 node 사이의 최단 경로
• 최악 시간 복잡도 : O(V^2)
• 평균 시간 복잡도 : O(E*logV)

#include <queue>
#define mp make_pair
priority_queue<pair<int,int>> pq;
// ...는 node 개수.
int dist[...];

// 시작점에서 시작점의 거리는 0이다.
dist[start]=0;
// priority queue에 pair가 입력되면 pair의 첫 번째 값으로 정렬된다.
// pq.first -> 가중치, pq.second -> node
pq.push(mp(0, start));
while(!pq.empty()){
	int now=pq.top().second;
    
    // 가장 작은 가중치를 우선으로 해야한다.
    // pq는 값이 큰 순서대로 정렬하는데, 이 점을 사용하여 가중치에 -를 붙이면
    // 가장 작은 값이 가장 앞으로 온다. 그래서 앞에 -를 붙인다.
    int now_dist=-pq.top().first;
    pq.pop();
    
    // now node에서 연결된 node를 모두 둘러본다.
    for(int i=0; i<v[now].size(); i++){
    	// 연결된 node를 next_node로 명명.
    	int next=v[now][i].first;
        int next_dist=v[now][i].second;
        
        // 만약 시작점 -> next_node 가중치가
        // 시작점 -> now_node -> next_node 가중치보다
        // 크다면!!! 값을 더 작은 값으로 업데이트 한다.
    	if(dist[next]>now_dist+next_dist){
        	dist[next]=now_dist+next_dist;
            // - 붙이는 거 잊지말긔.
            pq.push(mp(-dist[next], next));
        }
    }
}

2. Bellman-Ford (벨만포드 알고리즘)

• 음수 가중치
• 최악 시간 복잡도 : O(V^3)
• 평균 시간 복잡도 : O(V*E)

#define MX 999999999
int dist[...];
bool cycle=false;

for(int i=1; i<=n; i++) dist[i]=MX;

// start의 값은 아무거나 해도 된다.
dist[start]=0;

// 음수 가중치가 있으면 dist의 값이 반복할수록 줄어든다.
// 그래서 '최대 이 만큼만 돈다'는 제한을 걸어줘야 하는데
// 그 제한을 (node의 개수-1)만큼 제한한다. 그걸 나타내는 게 k.
// 아래 if(k==n)이면 cycle이 있다고 표시해주기 때문에 n까지 도는 걸로 설정했으나,
// 알고리즘 짜는 사람에 따라 k를 (n-1)로 제한해도 된다.
for(int k=1; k<=n-1; k++){
	for(int i=1; i<=n; i++){
    
    	int now=i;
        int now_dist=dist[i];
    	for(int j=0; j<v[now].size(); j++){
        	int next=v[now][j].first;
            int next_dist=v[now][j].second;
            
            // dist[i]가 MX 가지면 dist[next]는 갱신되지 못한다.
        	if(now!=MX && dist[next]>now_dist+next_dist){
            	dist[next]=dist[i]+next_dist;
                // 만약 최대 반복 횟수를 넘어서도 가중치 값이 바뀐다면,
                // 음수 cycle이 존재한다.
                if(k==n) cycle=true;
            }
        }
    }
}

3. Floyd-Warshall (플로이드 와샬 알고리즘)

• 모든 node 사이의 최단 경로 탐색
• k: 경유지, i: 출발점, j: 도착점
• 순서는 k > i > j 잊지말자!
• n(node 개수) 값이 작을 때만 가능. 시간 복잡도를 고려해야 한다.
• 평균 시간 복잡도 : O(V^3)

// dist 배열 초기화
// MX로 초기화 해줘야 최소값을 찾을 수 있다.
#define MX 999999999

for(int i=1; i<=n; i++){
	for(int j=1; j<=n; j++){
    	dist[i][j]= (i==j) ? 0 : MX;
    }
}

for(int k=1; k<=n; k++){
	for(int i=1; i<=n; i++){
    	for(int j=1; j<=n; j++){
        	dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

4. BFS

• 가중치가 없거나 모든 edge에 동일한 가중치
• 최악 시간 복잡도 : O(V^2)
• 평균 시간 복잡도 : O(V+E)

#include <queue>
queue<int> q;
int check[...];

q.push(start);
// 방문했음을 체크하는 배열
check[start]=1;
while(!q.empty()){
	int now=q.front();
    q.pop();
    for(int i=0; i<v[now].size(); i++){
    	int next=v[now][i];
    	if(!check[next]){
        	q.push(next);
            check[next]=1;
        }
    }
}

REF

[최단 경로 알고리즘] https://velog.io/@pul8219/%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C

VERSION 정보
ver1. 2022.06.30