가장 빠르게 도달 하는 방법
그리디 알고리즘 및 다이나믹 알고리즘의 한 유형
가장 짧은 경로를 찾는 알고리즘
예 )
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우
종류
- 다익스트라 최단경로 알고리즘
- 플로이드 워셜
- 벨만 포드 알고리즘
다익스트라 최단 경로 알고리즘
각 노드에서 현재까지의 최단거리 정보를 항상 1 차원 리스트에 저장하며 리스트를 계속 갱신
- 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로 구해주는 알고리즘
- 음의 간선이 없을 때 사용 가능
**가장 비용이 적은 노드**를 선택해 임의의 과정 반복- 원리
- 출발 노드를 정함
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 위 과정에서 3,4 반복
다익스트라 알고리즘 구현방법
- 구현하기 쉽지만 느림
- 구현하기 조금 까다롭지만 빠름
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"; }
}
}'Algorithm > C++' 카테고리의 다른 글
| [개념] 다이나믹 프로그래밍(동적계획법) (0) | 2020.10.11 |
|---|---|
| [개념] DFS/BFS (0) | 2020.10.09 |
| [개념] 이진탐색 (0) | 2020.10.09 |
| [개념] 정렬 알고리즘 (0) | 2020.10.01 |