최단거리 알고리즘 |
그래프(트리)에서 목적지까지의 최단거리를 찾는 알고리즘
주로 BFS, 다익스트라, 벨만포드, 플로이드-와샬 4가지의 알고리즘이 사용됨
| BFS | 다익스트라 | 벨만포드 | 플로이드 와샬 |
| 가중치가 없거나 있는데 모두 같을때 | 가중치가 모두 다를때 단 가중치가 모두 양수여야 함 |
가중치가 모두 다를때 가중치가 음수여도 됨 음의 사이클 유무 파악도 가능 |
가중치가 모두 다를때 가중치가 음수여도 됨 단, 음의 사이클이 없을때만 |
| Queue 사용 | 우선순위큐 사용 / 그리디기반 | DP기반 distance[n] = min(distance[n], distance[m] + E(m, n)) |
2차원배열 사용 DP기반 distance[i, j] =min(distance[i, j], distance[i, n] + distance[n, j]) |
| O(E) | O(ElogV) | O(VE) | O(V^3) |
| 하나의 특정 정점에서 다른 정점들까지의 최단경로를 구하는 1:N | 1:N | 1:N | 모든 정점들간의 쌍에 대한 최단 경로를 한번에 구하는 N:M |
| 그래프의 일부만 주어져도 사용 가능 |
그래프의 일부만 주어져도 사용 가능 |
그래프 전체가 주어져야 제기능 그래프가 무한하면 부적합할 수 있음 |
그래프 전체가 주어져야 제기능 그래프가 무한하면 부적합할 수 있음 |
| distances 사용 | distances 사용 | distances 사용 | distances 사용 |
| adj 사용 | adj 사용 | adj 미사용 | adj 미사용 |
| -1 사용 | INF 사용 | INF 사용 | INF / 2 사용 |
BFS |
가중치가 없는(혹은 모두 같은) 최단거리 알고리즘
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
std::vector<std::vector<int>> adj; // 그래프의 인접 리스트 표현
std::vector<int> distance; // 각 정점의 최단거리
std::vector<int> parent; // 최단경로를 기록하기 위해
// 만약 방문되었는지 확인하는 과정이 필요하다면 bool visited[] 사용도 고려하기
void bfs(int start)
{
std::queue<int> q;
distance[start] = 0; // 시작점은 자기 자신이니 거리가 0
q.push(start);
while (q.size()) {
int here = q.front();
q.pop();
for (int there : adj[here]) {
if (distance[there] == -1) { // visited를 대신하는건데 만약 한곳에 여러번 방문 가능한 구조라면 visited 사용하기
q.push(there);
distance[there] = distance[here] + 1; // 가중치 있으면 1대신 가중치
parent[there] = here; // 부모에 대한 정보를 추가
}
}
}
}
std::vector<int> shortestPath(int v) // v까지의 최단 경로 func
{
std::vector<int> path;
path.push_back(v); // 자기자신 넣고 시작
while (parent[v] != -1) {
v = parent[v];
path.push_back(v);
}
reverse(path.begin(), path.end()); // 자식부터 부모순으로 올라갔으니 역순으로 정리
return path;
}
int main()
{
int number_of_vertex, number_of_edge, start_vertex;
std::cin >> number_of_vertex >> number_of_edge >> start_vertex;
// 이 세줄에서 nov+1하는 이유는 보통 정점을 1번부터 세기때문
// 만약 0번부터 센다면 그냥 +1 안해도 됨
distance.resize(number_of_vertex + 1, -1); // 전부 -1로 초기화
adj.resize(number_of_vertex + 1);
parent.resize(number_of_vertex + 1, -1);
int u, v;
for (int i = 0; i < number_of_edge; i++) {
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(start_vertex);
// 최단 경로 출력하기
std::vector<int> sp;
int look_for;
std::cout << "찾고자 하는 노드 number : ";
std::cin >> look_for;
sp = shortestPath(look_for);
for (int i : sp) {
std::cout << i << ' ';
}
return 0;
}
다익스트라 |
1. 개념
경로에 가중치가 모두 같지 않다면 BFS로는 해결이 불가능함
아래 사진에서 1번노드에서 3번노드로 가는 최소비용은 1 -> 2 -> 4 -> 3의 경로로 2 + 4 + 3 = 9이지만 BFS라면 1 -> 3의 경로로 12의 비용으로 이동하게 됨
2. 로직
다익스트라 알고리즘은 그리디방식으로 현재 위치한 노드에서 가장 적은 가중치로 갈 수 있는 노드로 이동하면서 거리들을 계산한 후에 더 작은 비용이 나오면 갱신하는 방식
즉 1번에서 시작할때 가장 적은 비용으로 갈 수 있는곳은 2번이므로 2번으로 이동하면서 시작하는 그리디한 방식
BFS의 경우 정점에 접근한 순서대로 큐에 들어가고 나오므로 나중에 더 짧은 경로를 발견해도 새치기를 할 수 없는 반면 다익스트라 알고리즘은 나중에 더 짧은 경로가 나오면 큐에서 새치기를 하기 위해 우선순위큐를 사용함
위 알고리즘을 사용해서 위의 그래프를 탐색한다면 시작점 1을 방문하고나서 우선순위큐에 (2, 2)와 (12, 3)이 들어가게 됨(우선순위 큐에서 정렬을 편하게 하기 위해 누적거리를 앞에 둠)
그 후 탐색을 계속 하다보면 (9, 3)도 우선순위큐에 들어가게 되며 distance[3]는 9로 갱신되고 이미 큐에 들어가있는 (12, 3)이 꺼내졌을때는 distance[3]와 비교해서 더 크므로 무시하게 됨
알고리즘 구성
1) 각 정점까지의 최단 거리를 저장하는 배열 distance[]를 만들고, 시작점의 distances값은 0을 넣고 그 외의 점들은 INF같은 아주 큰 값으로 초기화
2) BFS에서는 큐에 정점의 번호를 넣었지만, 다익스트라 알고리즘에서는 (해당 정점까지의 누적거리, 정점의 번호)를 pair로 넣음
3) 반복문을 돌면서 큐에서 원소를 하나 꺼내서 해당 원소에 인접한 정점들을 검사하고 이때 distance[]에 기록된 경로보다 비용(현재 정점까지의 누적거리 + 간선의 가중치)이 더 작다면 distance[]를 갱신하고 큐에 (정점의 누적거리와 정점의 번호)를 넣음
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#define INF 2147483647
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> distance;
std::vector<int> parent;
std::vector<int> dijkstra(int start) {
std::priority_queue< std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<> > pq;
// (현위치까지의 distance, 현위치) 형태로 저장
distance[start] = 0; // 시작지점의 거리는 0
pq.push(std::make_pair(0, start)); // (현위치까지의 distance, 현위치)
while (pq.size()) {
int here = pq.top().second; // 현재 방문한 정점
int here_cost = pq.top().first; // 방문한 정점의 dist 값
pq.pop();
if (here_cost > distances[here]) continue; // 시간단축
for (auto& p : adj[here]) {
int there = p.second; // 조사할 다음 정점
int there_cost = here_cost + p.first; // 현재 방문한 정점을 거쳐서 다음 정점을 갈때의 비용
if (there_cost < distance[there]) { // 기존 비용보다 현재 방문한 정점을 거친 비용이 더 싸다면
distance[there] = there_cost; // 갱신
pq.push(std::make_pair(there_cost, there)); // pq에 저장
parent[there] = here;
}
}
}
return distance;
}
std::vector<int> shortestPath(int v)
{
std::vector<int> path;
path.push_back(v); // 자기자신 넣고 시작
while (parent[v] != -1) {
v = parent[v];
path.push_back(v);
}
reverse(path.begin(), path.end());
return path;
}
int main()
{
int number_of_vertex, number_of_edge, start_vertex;
std::cin >> number_of_vertex >> number_of_edge >> start_vertex;
// 이 세줄에서 nov+1하는 이유는 보통 정점을 1번부터 세기때문
// 만약 0번부터 센다면 그냥 +1 안해도 됨
distance.resize(number_of_vertex + 1, INF); // 전부 INF로 초기화
adj.resize(number_of_vertex + 1);
parent.resize(number_of_vertex + 1, -1);
for (int i = 0; i < number_of_edge; i++) {
int from, to, cost;
std::cin >> from >> to >> cost;
adj[from].push_back(std::make_pair(cost, to)); // vertex, cost여도 상관없지만
adj[to].push_back(std::make_pair(cost, from)); // 일관성을 위해 이렇게 쓰는게 더 편한 듯
}
// 시작점부터 각 점까지의 최소비용 출력하기
std::vector<int> distances = dijkstra(start_vertex);
for (int i = 1; i < distances.size(); i++) {
std::cout << "시작점부터 " << i << "노드까지의 거리 : " << distances[i] << '\n';
}
// 최단 경로 출력하기
std::vector<int> sp;
int look_for;
std::cout << "찾고자 하는 노드 number : ";
std::cin >> look_for;
sp = shortestPath(look_for);
for (int i : sp) {
std::cout << i << ' ';
}
return 0;
}priority_queue는 내림차순정렬이 default인데
다익스트라 알고리즘에서는 오름차순 정렬이 필요함
방법1)
std::priority_queue< std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<> > pq;
형태로 우선순위큐를 선언
방법2)
std::priority_queue<std::pair<int, int>> pq;로 그냥 선언하고
pq.push(std::make_pair(-thereCost, there));로 -로 넣고
int cost = -pq.top().first;로 빼올때 -를 다시 붙여버리는 방법도 있음
※ queue는 front()로, priority_queue는 top()으로 값을 확인한다.
아마 priority_queue는 힙트리구조라 그런게 아닌가 싶다.
벨만포드 |
1. 개념
다익스트라와 마찬가지로 시작정점인 1번정점에서 출발해서 각 정점까지의 최소비용을 계산한다
다만 다익스트라 알고리즘은 그리디하게 동작해서 현재의 노드에서 가장 가까운 값으로 갈 수 있는 노드로 진행하는 반면
벨만포드는 DP개념으로 작동해서 모든 경우의 수를 다 탐색해가면서 최소비용을 찾는다
기본적으로 벨만포드는 다익스트라 알고리즘보다 더 오래 걸리는 탐색방법이므로 모든 가중치가 양수인 경우 다익스트라 알고리즘을 쓰는것이 좋다
하지만 가중치에 음수가 있다면 다익스트라는 사용불가능하므로 벨만포드 알고리즘을 사용하며 벨만포드는 음의 사이클이 있는지 확인까지 할 수 있다
2. 로직
1) 모든 간선(edge)들을 탐색하면서 간선이 잇는 출발정점의 거리값이 INF가 아니라면 해당 출발 정점에서 인접한 정점들까지의 최소비용을 비교해서 업데이트한다
2) 1번의 과정을 (정점의갯수 - 1) 만큼 반복한다
(정점의 갯수 - 1)회 반복하는 이유는 최단거리로 이동하는 경우 거쳐갈 수 있는 최대의 정점의 갯수가 (정점의 갯수 - 1)개이기 때문
좀 더 구체적으로 설명해보자면
최단거리를 구하기 위해 초기 세팅을 한다면 출발점이 1번노드라면 1번노드의 누적거리값은 0이고, 나머지는 INF로 초기화하고 시작할 것이다
즉 1번노드의 거리값은 INF가 아니며 1번노드를 출발점으로 하는 간선들을 탐색해나가며 업데이트 하는 것
알고리즘을 따라가보면
1) 간선 A는 1 -> 2로 가는 간선이며 1의 누적거리값은 INF가 아니고, 2의 비용이 INF이므로 정점2의 비용이 3으로 업데이트된다.
2) 간선 B는 1 -> 3로 가는 간선이며 위와 같은 이유로 3번정점의 비용은 2로 업데이트된다.
3) 간선 C는 1 -> 4로 가는 간선이며 위와 같은 이유로 4번정점의 비용은 5로 업데이트된다.
4) 간선 D는 2 -> 3로 가는 간선이며 정점 2는 A간선을 계산할때 누적거리가 계산되어 INF가 아니게 된 상황이다. 또한 정점3은 간선B를 계산할때 비용이 2로 업데이트되어있다.
즉 간선 D의 상황을 보면 1 -> 2에서 3의 비용, 2 -> 3에서 3의 비용으로 1 -> 3의 비용은 6이 되는데 이는 기존의 값인 2보다 크므로 업데이트하지 않는다.
5) 간선 E는 3 -> 4로 가는 간선이며 3은 계산되어 누적거리가 INF가 아니고, 현재 4의 비용은 5이다
즉 1 -> 3의 비용 2, 3 -> 4의 비용 -4로 1 -> 4의 비용은 -2가 되므로 기존에 4의 비용이었던 5보다 -2가 작으므로 정점 4의 비용은 -2로 업데이트된다.
6) 간선 F는 4 -> 2로 가는 간선이며 4는 계산된 정점이며, 현재 2의 비용은 3이다.
즉 1 -> 4의 비용 -2, 4 -> 2의 비용 -4로 1 -> 2의 비용은 -6이 된다.
기존의 2의 비용이었던 3보다 -6이 작으므로 정점 2의 비용은 -6으로 업데이트된다.
이렇게 모든 간선을 탐색하고 나면 각 정점들의 최소비용이 아래와 같이 업데이트된다.
이게 1번 완료한거고 (정점의 갯수 -1)회 반복해야하므로 여기선 3번 반복해야 하니 아직 2번 남았다.
이번 사이클에선 모든 정점이 이미 한번이라도 계산된 정점이므로 모든 간선에 의해 업데이트가 일어날수도 있고 일어나지 않을 수도 있다.
또 한사이클 돌아보자
1) 간선A는 3과 -6의 비교이므로 업데이트되지 않는다.
2) 간선B는 2와 2의 비교이므로 업데이트되지 않는다.
3) 간선C는 5와 -2의 비교이므로 업데이트되지 않는다.
4) 간선D에 의해 업데이트가 발생한다.
D는 2 -> 3을 이어주는 비용3의 간선인데 1 -> 2의 비용이 -6이고 2 -> 3의 비용이 3이므로 1 -> 3의 비용은 -3이다. 즉 정점3의 최소비용은 2와 -3의 비교이므로 -3이 된다.
5) 간선E에 의해 업데이트가 발생한다.
간선 E는 3 -> 4를 이어주는 간선인데 현재 4의 최소비용은 -2인 상태이고
1 -> 3은 -3이고 3 -> 4는 -4이므로 1 -> 4의 최소비용은 -7과 -2의 비교이므로 -7로 업데이트된다.
6) 간선F에 의해 업데이트가 발생한다.
간선 F는 4 -> 2를 이어주는 간선인데 현재 2의 최소비용은 -6인 상태이고
1 -> 4는 -7이고 4 -> 2는 -4이므로 1 -> 2는 -11로 -6보다 작으므로 업데이트된다.
이렇게 한 사이클을 또 반복하고난 결과는 아래와 같다.
이제 한사이클 더 반복해야한다. 근데 이미 개념은 이해했을테니 여기선 생략하는걸로 하고(실제 코드에선 당연히 한번 더 돌아가야 함) 한사이클 더 반복한 결과는 아래와 같다.
즉, 위의 그래프 결과가 N - 1회 반복했을때의 결과이다.
여기서 주목할점은 2번정점의 최소비용은 N - 1회 반복했을때 -16이다.
그런데 만약 한사이클을 더 반복한다면 2 -> 3 -> 4 -> 2로 한바퀴 더 돌면 -21이되고, 또 돌면 -26이 되고 계속 한없이 작아지게되고 결국 마이너스 무한대가 된다.
이런 상황을 음의 사이클/음수 사이클이라고 한다.
즉, 음의 사이클이 존재하는지 판별하는 방법은 N - 1번의 사이클을 돌고난 후 결과에서, 딱 한사이클을 더 돌아봤을때 결과가 바뀌는게 있다면 음의 사이클이 존재하는 것이고, 결과가 바뀌는게 없다면 음의 사이클이 없다는 뜻이다.
#include <vector>
#include <iostream>
#define INF 2147483647
std::vector<Edge> edges;
std::vector<int> distance;
class Edge {
public:
int from;
int to;
int cost;
Edge(int f, int t, int c) {
from = f;
to = t;
cost = c;
}
};
void Bellman_Ford(int nov, int start)
{
distance[start] = 0;
for (int i = 0; i < nov - 1; i++) { // (vertex의 갯수 - 1)회 반복
for (auto& e : edges) {
int From = edges[j].from;
int To = edges[j].to;
int Cost = edges[j].cost;
if (distance[From] == INF) continue; // 시작점의 누적거리가 INF면 넘기고
if (distance[To] > distance[From] + Cost) distance[To] = distance[From] + Cost; // 갱신
}
}
// 음의 사이클이 존재하는지 확인해보기
for (auto& e : edges) {
int From = edges[i].from;
int To = edges[i].to;
int Cost = edges[i].cost;
if (distance[From] == INF) continue;
if (distance[To] > distance[From] + Cost) { // 비용이 더 줄어서 갱신되고있다면
std::cout << "음의 사이클이 존재\n";
return;
}
}
std::cout << "음의 사이클이 존재하지 않음.\n";
for (int i = 1; i < distance.size(); i++) {
std::cout << "시작점부터 " << i << "노드까지의 거리 : " << distance[i] << '\n';
}
}
int main()
{
int number_of_vertex, number_of_edge, start_vertex;
std::cin >> number_of_vertex >> number_of_edge >> start_vertex;
distance.resize(number_of_vertex + 1, INF); // 전부 INF로 초기화
for (int i = 0; i < number_of_edge; i++) {
int from, to, cost;
std::cin >> from >> to >> cost;
edges.push_back(Edge(from, to, cost));
}
Bellman_Ford(number_of_vertex, start_vertex);
return 0;
}
플로이드 와샬 |
1. 개념
모든 정점에서 모든 정점으로의 최단 경로를 한번에 구하고
음수 가중치도 사용 가능하지만 음의 사이클이 있을때는 사용이 불가능
모든 쌍을 표현하는 행렬(이차원배열)을 선언하고 DP방식으로 각각 원소들의 최단거리를 업데이트해나감
정점i에서 정점j로 가는데 정점n을 경유해서 가는것이 더 빠르다면 그 정점을 거쳐서 가는것으로 업데이트
점화식으로 표현하면 distance[i, j] = min(distance[i, j], distance[i, n] + distance[n, j])
2. 로직
1) 행렬 초기화 : 그래프모양대로 거리값을 초기화하며 자기 자신은 0, 인접한 정점은 가중치값, 직접인접하지 않은 노드는 INF로 초기화
2) 거쳐갈 정점들을 처음부터 검사해서 거쳐가는것이 더 최단경로라면 업데이트
풀어서 설명해보자면
위 그래프를 예시로 설명한다면 초기화한 행렬은 아래와 같다.
| 0 | 5 | INF | 8 |
| 7 | 0 | 9 | INF |
| 2 | INF | 0 | 4 |
| INF | INF | 3 | 0 |
이 테이블은 현재까지 계산된 최소비용을 의미하며 이 테이블을 계속 갱신해나가서 최종적으로 모든 최소비용을 구하는 것
이제 각 정점을 거쳐가는 경우를 기준으로 갱신해나간다.
1) 노드 1을 거쳐가는 경우
| 0 | 5 | INF | 8 |
| 7 | 0 | XXX | XXX |
| 2 | XXX | 0 | XXX |
| INF | XXX | 3 | 0 |
위의 XXX부분만 갱신하면 된다. 왜냐하면 다른 값들은 노드1과 직접 연결되어있거나, 자기 자신과의 거리이므로
이제 i에서 j로 가는 최소비용 vs ( i에서 노드 1로 가는 비용 + 노드 1에서 j로 가는 비용 ) 둘을 비교하는 것
위 표에서 [2, 4]자리의 경우를 예로 들자면 D[2, 4] vs (D[2, 1] + D[1, 4]) 중 작은 값으로 갱신된다.
기존엔 INF값이 들어있으므로 D[2,1] + D[1,4] 값인 7+8인 15가 들어가는 것
이런식으로 위의 5자리를 갱신하고 나면
| 0 | 5 | INF | 8 |
| 7 | 0 | INF | 15 |
| 2 | 7 | 0 | 4 |
| INF | INF | 3 | 0 |
2) 노드 2를 거쳐가는 경우
점화식이 같으니 위처럼 갱신하면 되고 또 3번노드 4번노드 쭉 갱신하면 완료
코드로 표현하면
#include <iostream>
#include <vector>
#define INF (2147483647 / 2) // 23line에 distance간의 덧셈이 있어서 2147483647로 쓰면 오버플로우나서 음수가 되서 항상 작아지므로 오류발생함
std::vector<std::vector<int>> distance;
void FloydWarshall(int nov)
{
// 시간복잡도 V^3
// i, j, k = 1은 정점 1번부터 세는 경우, 0번부터 센다면 0으로
for (int k = 1; k < nov; k++) // k 는 거쳐가는 정점
for (int i = 1; i < nov; i++) // i 는 행 (출발 정점)
for (int j = 1; j < nov; j++) // j 는 열 (도착 정점)
distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
// 결과 출력
for (int i = 1; i < nov; i++) {
for (int j = 1; j < nov; j++) {
std::cout << distance[i][j] << ' ';
}
std::cout << '\n';
}
}
int main()
{
int number_of_vertex, number_of_edge; // M:N이므로 시작정점은 필요없음
std::cin >> number_of_vertex >> number_of_edge;
// nov+1하는 이유는 보통 정점을 1번부터 세기때문, 만약 0번부터 센다면 그냥 +1 안해도 됨
distance.resize(number_of_vertex + 1, std::vector<int>(number_of_vertex + 1, INF)); // 전부 INF로 초기화
for (int i = 0; i < number_of_vertex + 1; i++) { //★ 여기를 자주 빼먹으니 주의, 자기자신까지의 거리가 0이라면 반드시 작성하기
distance[i][i] = 0; // 자기자신까지의 거리는 0
}
for (int i = 0; i < number_of_edge; i++) {
int from, to, cost;
std::cin >> from >> to >> cost;
distance[from][to] = cost;
}
FloydWarshall(number_of_vertex + 1);
return 0;
}
※ 참고문헌
https://ansohxxn.github.io/algorithm/floyd/