[알고리즘] 최단경로(Shortest Path Problem) - 1

최단경로(Shortest Path Problem) - 1

이번시간에는 그래프 알고리즘 중에서 가장중요하고 유명한 최단 경로에 대해 알아보자

최단 경로는 이름 그대로 가장 짧은 경로를 찾는 것이다.

먼저 최단경로 문제에서는 가중치를 가진 그래프가 주어진다.

사실 최단 경로에서는 방향/무방향이 무의미하다. 따라서 방향 그래프를 예시로 설명을 진행한다.

경로의 길이를 정의해야하는데, 길이는 그 경로상에 있는 모든 가중치들의 합이다.

따라서 최단 경로는 U에서 V로가는 가장 짧은 길이를 말한다.

그러므로 이렇게 U에서 V까지의 최단 경로를 ∂(U,V)라고 정의한다.

최단 경로 문제의 목적은 ∂(U,V)를 구하는 것이다.

최단 경로의 문제의 유형에 따라 구분을 할수 있다.

먼저 하나의 출발 노드로부터 모든 노드의 최단 경로를 찾는 single-source이다.

single-source로 가장 유명한 것이 다익스트라 알고리즘이다.

이는 one to all 최단 경로 알고리즘이라고 불린다.

이와는 반대로 single-destination은 목적지 t가 주어지면 

모든 노드로 부터 목적지 t까지의 최단 경로를 찾아내는 것이다.

만약, 무 방향 그래프이면 이 문제의 해답은 single-source 문제와 같다.

single-pair는 주어진 하나의 출발 노드 s로 부터 하나의 목적지 노드 t까지의 최단 경로이다.

pair라는 말 그대로, 출발 노드와 목적지 노드가 쌍을 이루게 된다.

사실상 현실적으로 가장 효율성, 실용성이 있는 문제가 된다.

All-pairs는 모든 노드쌍에 대한 최단 경로를 찾는 것이다.

다른 이름으로 all-to-all이라고 불린다.

가장 유명한 것이 플로이드 알고리즘이다.

알고리즘을 살펴보기 전에 짚고 넘어가야할것이 음수 가중치이다.

말그대로 가중치가 음수인 상황인데, 거리가 음수인 경우가 없으므로

 많은 최단경로 알고리즘이 음수 가중치(negative weight)가 없다고 가정한다.

그러나 항상 그렇지는 않다. 따라서 음수 가중치가 존재할수 있다는 것이다.

더 나아가서 음수 사이클(negative cycle)은, 모든 경로의 합, 길이가 음수가 나오게 된다는 것이다.

사이클이 돌면 돌수록 길이가 짧아지므로 현실적으로 말이 되지 않다.

따라서 음수 사이클이 있으면 최단 경로가 정의 되지 않는다.

또한 최단 경로가 가지고 있는 가장 기본적인 특성에 대해 알아보자.

당연한 소리일지도 모르지만, 최단 경로의 부분 집합도 부분 집합의 끝에서 끝까지의 최단 경로이다.

결국 최단 경로는 모든 최단 경로들의 합이 되는 것이다.

또한 최단 경로는 사이클을 포함 하지 않는다.

물론 음수 사이클을 가지지 않는다는 조건 하에서 말이다.

사이클을 포함하지 않는 이유는 최단 경로로 가는데 굳이 사이클을 돌아서 갈 필요가 없기때문이다.

최단 경로 알고리즘의 첫번째로 Single Source, One-to-all 문제를 알아보자

출발점을 포함하는 모든 노드들에 대해서 d[v]값을 유지한다.

이는 S로 부터 V까지가는 경로의 최단 길이에 대한 추정치의 의미이다.

처음부터 최단 거리에 대한 것을 모르기 때문에, 노드까지 가는 데이터가 많아지면서

d[v]는 현재까지 찾은 최소한의 경로의 길이가 되며 꾸준히 업데이트된다. 

따라서 d[s]=0로 시작하고, 데이터가 없는 다른 노드들에 대해서는 d[v] = 무한대가 된다.

그러다가 결국 d[v]는 최종적으로 ∂(s, v)가 된다.

그 다음 최단 경로 길이의 문제가 길이만을 구하는 것이 아니라 실제 경로 자체를 구해야한다.

따라서 이를 위해 π[v]를 표현하며, s에서 v까지 최단 경로상에서 v의 직전 노드를 의미한다.

같은 원리로 처음에는 그런 노드가 없으므로 π[v] = NIL이다. 

다음으로 대부분의 최단 경로에서 기본적으로 제공되는 연산이 Relaxation이다.

위의 그림에서 u까지의 최단경로는 d[u] = 5, v까지의 최단 경로는 d[v] = 9가된다.

그런 상황에서 u에서 v로 가는 엣지에 대해서 relax한다는 것은 최단 경로를 최신화 한다는것이다.

즉, 기존에 자신이 알고 있는 경로보다 더 나은 경로를 하나 발견하고 적용한다는 것이다.

(a)의 그림을 보면 d[v]=9였다가 더 짧은 가중치 2의 경로를 발견하고 d[v] = 7이 되었다.

(b)에서는 가중치를 적용하더라도 기존의 값보다 최적화 되지 않으니 적용하지 않는다.

(슈도 코드에서 w란 weight function이며, 모든 엣지들에 대해서 weight를 부과하는 함수이다.)

실제로 대부분의 single source 알고리즘은 relax 연산을 반복적으로 수행함으로써 최단 경로를 찾는다.

알고리즘 간의 차이는 relax 연산을 어떤 엣지에 대해서, 어떤 순서로 하느냐에 따라 발생한다.

위의 슈도 코드는 일종의 기본적인 single-source 알고리즘이다.

일단 첫번째 스텝은, 위에서 언급했듯이 값을 초기화 하는것이다.

다음에 코드를 잘보면 모든 엣지에 대해서 한번씩 relax 연산을 하게 된다.

엣지들이 여러개 이므로, 어떤 엣지부터 반복하느냐가 구체적으로 된다면 알고리즘이 확정된다.

이를 한번하고 끝나는 것이 아니라, 아무 변화가 없어질때 까지 계속 반복해야한다.

변화가 없다는 것은, d[v]값이 업데이트 되지 않을 때, 최단 경로가 안정화 되었을 때를 의미한다.

위의 그림을 잘 살펴보면 앞서 본 2개의 질문에 대해 대답할 수 있다.

결론부터 말하자면 n-1의 반복으로 충분하다는 것인데 왜 이런 횟수가 나온걸일까.

우선 노드가 n개 일 때 엣지의 최대 개수는 n-1개가 된다.

왜냐하면 최단 경로는 사이클을 포함하지 않으므로 노드를 2번 지나갈수 없다.

따라서 모든 노드를 거치더라도 엣지의 개수는 n-1개가 된다.

따라서 모든 엣지들에 대해 relax를 하는 것을 한 라운드라고 할 때, 첫번째 라운드에서 d[v1]은 찾아진다.

왜냐하면 첫번째 라운드에서 모든 엣지들에 대해 relax를 하기 때문에, 

v1노드 까지의 최단거리는 확정된다. 

그리고 두번째 라운드에서 v2 까지의 최단 경로가 찾아지며

세번째 라운드에서는 v3 까지, i 번째 라운드에서는 d[vi]까지의 최단 경로가 찾아진다.

그리고 위에서 말한 엣지의 개수는 n-1개 이므로, n-1번의 반복으로 최단 경로가 찾아진다.

사실은 이렇게 반복하는 것이 Bellman-ford 알고리즘이며 슈도 코드는 위와 같다.

앞서 살펴본 일반적인 알고리즘과 다른 점은 for문의 반복이 n-1로 고정 되어 있는 것이다.

또한, Bellman-ford 알고리즘은 음수 사이클이 있는 경우에도 이를 탐지 할 수 있다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘