최단거리류 알고리즘에 대해서(다익스트라,벨만포드,플로이드 등등)

많은 문제들이 최소 비용, 최단거리 등에 집착한다. 하지만 막상 수많은 최단거리, 최소 비용에 대한 문제들을 보면

어떤 알고리즘을 써서 풀어야하지...? 하는 생각이 들고 생각나는대로 문제를 풀면 시간초과 혹은 오답이 나오면 멘붕이 

오곤한다..

이번 글에선 "최단 거리" 에 대해서와, 언제, 어떤걸 써야하는지에 대해 간략하게 정리해 보겠다.

 

디테일한 설명전 간단한 요약을 먼저 하자면

 

bfs: 간선에 가중치가 없다(단위길이) , 즉 비용이 아닌 거치는 횟수가 요구될 때. 

다익스트라: 특정 시작점 <> 모든 지점 간의 최단거리

플로이드와샬: 모든 시작점 <> 모든 지점 간의 최단거리

벨만포드: 최단거리에서 음수 간선, 등으로 인하여 계속해서 최단거리를 줄여나가는지 "감지" 해야하는 경우

 

정도로 요약할 수있다.

 

1)가중치가 존재하지 않는 문제

     모든 간선의 비용이 "1" 로 고정되는 단위길이다. 이 경우, bfs를 통한 최단거리를 찾으면 된다. 

 

2)가중치가 존재하고, 사이클이 생기지 않는 문제 + 한개, 혹은 특정 개수의 시작점만 존재할시

    흔히들 "음의 가중치가 없는 그래프" 에서 다익스트라를 사용한다. 하지만 엄밀히 말하면 "사이클이

    생기지 않는 문제들" 에서만이다.

    문제들중 이를 살짝 비틀어 "최대 이득" 을 찾는 문제가 나오곤하는데, 이는 최단거리와 상당히 유사한

    매커니즘으로 돌아가지만, "양의 사이클" 이 생길 수 있다는 문제가 다르다. 왜 이런 차이가 생길까?

    최단거리의 경우 우리는 최단거리를 찾기 위하여, 작은 값들로 계속해서 갱신해 나가므로,

    간선에 음수가 존재할 경우, 어떤 사이클을 돌면 계속해서 최소 값이 갱신될 수 있다. 

    ex: b>c  간선 값이  3   c>b 간선 값이 -4 일경우 b,c,b,c,를 무한히 돌면 계속해서 원래 값에서 -1이 되므로 무한히

    값이 갱신 될 것이다. 하지만 "최대 이득" 즉, 최대값으로 갱신해나가야 하는 문제들은 b>c 2 c>b-1 로 사이클이

    계속해서 +1이 될경우 계속해서 이득을 보는 해당사이클을 통해 값을 갱신해 나가므로, 무한한 양의 사이클이

    생기게 된다. 따라서 정확히 말하면 다익스트라는 "무한한 사이클이 생기지 않는 문제" 에서만 사용해야한다.

 

 

 

3)모든 정점간의 최단 거리를 구해야할때

    1,2,3  3개의 정점이 있다고할 때  1<>2   2<> 3   1<>3 과 같이 각각의 최단거리를 구해야할 땐

    플로이드-와샬 알고리즘을 통하여 각각의 최단거리를 구해야한다.   

    플로이드는 한번에 모든 거리들을 구해 놓는 만큼, "모든 각정점들 간의 최단거리" 와 같이

    출발, 도착지가 특정되 있지 않고 모든 거리들을 찾아야하는 경우 사용하고, 만약 숫자가 작아 시간초과가

    나지 않을 것 같은경우, 구현이 쉽다는 장점을 활용하여 구현 시간을 줄이기위해 사용하는 경우도 있다.

 

 

 

 

4)가중치가 존재하고, 사이클이 생길 수 있는 문제 

     벨만포드 알고리즘을 사용하면 된다. 벨만포드는 다익스트라와 다르고 플로이드-와샬과 유사하게 시작> 도착을

찾는 것이 아닌, 모든 최단경로를 찾는 알고리즘이다. 단 플로이드-와샬과 다르게 '정점' 기준이 아닌 '간선' 기준으로

모든 경로를 갱신한다.  모든 간선을 기준으로 계속해서 경로를 갱신하는데,  V개의 정점이 있다면 V-1개의 간선이 최대로 생길 것이다 . 따라서   간선을 통한 최단거리 갱신을 V-1번 반복하여 최단 거리를 찾는데, 만약  V-1번 이후에 1번이라도 갱신이 일어난다면 사이클이 발생하는 것 (1> 2 > 3 > 1 > 2 >3 > 1 .......) 

 

> 백준 11657 타임머신문제를 확인 해보자!

 

    여기서 주의할 점이 벨만포드는 "사이클이 존재하는가" 만 확인 가능하다. 즉

    사이클을 감지하기만 하면 되는 문제들은 벨만포드만 사용하면 되지만, 그 사이클이 결과값에 영향을 미치는지

    확인해야하는 문제는 구할 수 없다. 1219 오민식의 고민이 대표적인 이러한 케이스 중 하나이다. 

    해당 문제를 확인해보고 오자!

    11657 타임머신은 음수사이클이 존재하면 각 도시에 도달하는 값을 출력할 필요가 없는데, 사실 단지 난이도를

    낮추기 위해 이럴 뿐이다. 1219 는 앞서 말한 최대이윤에 대한 이야기, 그리고 각 위치에 도달하는 최대이윤 거리를

    찾아야 하므로 추가로 생각할 부분이 2개나 더있다.

 

     1)최단거리> 최대 이윤 으로

 

     2)무한 사이클(이 경우 최대이윤 문제지만 특이하게 음의 사이클을 찾으라고 한다. 만약 최대이윤, 양의 사이클에 대       한 문제를 풀고 싶다면 1738 골목길을 풀어보자..!)이 결과 값에 영향을 주는가?  (사이클이 있어도, 그 사이클을 통        해서 도착지로 도달 할 수 없다면, 의미가 없다.)  이를 알아보는 방법은 경로 역추적, 혹은 dfs를 통한 탐색이 있는데,      아래 코드는 dfs를 통한 탐색이다.

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF -987654321
using namespace std;

typedef struct { int u, v, w; }edge;
vector<edge> e;
int n, m, graph[105][105], city[105], pre[105], s, f;
long long dist[105];
bool visit[105];



bool dfs(int cur) {//cur에서 f(도착지) 까지 도착가능한가?>
	if (cur == f)return true;
	visit[cur] = true;
	bool chk = false;
	for (auto x : e) {
		if (x.u == cur && !visit[x.v]){
			if(!chk)//만약 아직 도착지로 가는 길 못찾았을때   >> 중요 if(!chk) 없으면 chk=true즉 도착지 경로를 찾아놓고 다시 chk=false(틀린경로 탐색) 로 돌아올수있다.
				chk = dfs(x.v);//다음행선지 탐색
		}
	}
	return chk;
}

int main() {
	scanf("%d%d%d%d", &n, &s, &f, &m);
	fill(&dist[0], &dist[n + 1], INF);

	for (int i = 0, u, v, w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		e.push_back({ u,v,w });
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &city[i]);
	}

	dist[s] = city[s];
	pre[s] = -1;


	//벨만포드.
	for (int k = 0; k < n - 1; k++)
		for (auto x : e) {
			if (dist[x.u] != INF && (dist[x.v] < dist[x.u] - x.w + city[x.v]))
				dist[x.v] = dist[x.u] - x.w + city[x.v];
		}

	if (dist[f] == INF)printf("gg");//도달불가
	else {

		for (auto x : e) {
			if (dist[x.u] != INF && (dist[x.v] < dist[x.u] - x.w + city[x.v]))
				if (dfs(x.u)) {//  dfs를 통해 음수사이클을 가진놈이 도착지로 도달가능한지 체크, 만약 도달가능시..
					printf("Gee");
					return 0;
				}
		}
		printf("%lld", dist[f]);
	}
	return 0;
}

 

가능하다면 1738 골목길 문제도 꼭! 풀어보자. 최단거리 문제의 집약체이다. 이 문제는 설명할 것이 많아 따로 설명을 올리겠다...

 

 

틀린부분, 이해가 되지 않는 부분은 언제나 댓글로 알려주세요..!