[알고리즘] SSP(1) - 단일 출발지 최단 경로 (Single Source Shortest Path)

1. 단일 출발지 최단 경로( Single Source Shortest Path )

단일 출발지 최단경로란 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것입니다.

그래프를 보시면 v1에서 v4로 가려면 두 가지의 경로가 존재합니다.

시작정점을 v1이라 할 때, v1에서 v2, v3까지 도달하는데 걸리는 비용을 알고 있다고 가정하면, 최단 경로는 두 경로 중 비용이 적은 경로를 선택하는 것입니다.

• v1 -> v2 -> v4
• v1 -> v2의 비용은 5이고, v2 -> v4의 비용은 2이므로 5 + 2 = 7의 비용이 걸립니다.
• v1 -> v3 -> v4
• v1 -> v3의 비용은 3이고, v3 -> v4의 비용은 9이므로 3 + 9 = 12의 비용이 걸립니다.

따라서 v1 -> v4의 두 경로 중 비용이 적은 1번을 선택하는 것이 v1에서 v4의 최단 경로입니다.

시작정점을 v1이 아니라 저 멀리서부터 왔다고 생각해보면, 최단 경로는 직전 정점까지의 경로 비용에 영향을 받는다는 것을 알 수 있습니다.

SSP는 단일 출발지에서 최단경로를 구하는 것입니다.

단일 출발지란 꼭 특정 하나의 정점이여만 한다는 것이 아니라, 모든 정점이 선택지가 될 수 있는데 그 선택된 정점에 대해서 각 정점까지의 최단경로를 구한다는 것입니다.

다음에 살펴볼 주제 ASP( All Pair Shortest Path )는 모든 정점끼리의 최단 경로를 계산합니다.

즉, SSP는 1차원 배열로써 각 정점까지 경로의 비용을 표현할 수 있지만, ASP는 2차원 배열이 필요합니다.

이후의 글을 읽으시면 이해가 될 것이니 일단은 그냥 넘어가겠습니다.

또 다른 특징으로 SSP에서는 음의 가중치를 생각할 수 있습니다.

음의 가중치를 허용하여 SSP를 구하는 알고리즘은 Bellman-Ford 알고리즘이고,

음의 가중치를 허용하지 않고 SSP를 구하는 알고리즘은 Dijkstra's 알고리즘입니다.

두 알고리즘을 살펴보기 전에 두 알고리즘에서 사용되는 Relaxation에 대해서 알아보겠습니다.

2. Relaxation

를 정점 v까지의 최단 경로 추정 값이라하고 를 정점 s에서 v까지의 실제 최단경로 비용이라고 할 때,

Relaxation이란 값이 의 상한이 되도록 유지하는 것을 의미합니다.

는 를 조정하면서 도달해야 할 목적지 입니다. 즉 아직 알 수 없는 값이죠.

SSP는 결국 를 조정하는 것이 핵심이며, 이렇게를 조정하는 함수를 Relax라고 합니다.

Original을 보시면 가 9입니다.

이 값은 SSP를 진행하면서 얻어진 최단 경로 추정 값입니다.

즉 임시 최단경로 값이니까 언제든 변할 수 있는 값이죠.

경로를 구하는 방법은 이전 정점( v1 )까지의 경로 비용과 연결된 가중치의 비용을 더하는 것입니다. 

그래서 이 5이고, 연결된 간선의 가중치가 2이므로 는 7입니다.

기존에 추정 값 9보다 더 작은 비용이므로 를 7로 변경합니다.

이렇게 비교 연산을 수행하는 것을 Relax라 합니다.

위의 그림에서는 Relax의 결과로 추정 값이 변경되었네요.

이 그림은 가 6입니다.

이 5이고, v2와 연결된 가중치가 2이므로 는 7입니다.

그런데 이미 는 6으로 7보다 더 낮은 비용으로 계산되어 있습니다.

이 때는 값을 변경시키지 않는 Relax를 수행합니다.

Relax란 목적지 정점( v2 )의 추정값과 직전 정점 ( v1 )의 추정값 + 간선의 가중치를 비교해서 목적지 정점의 추정 값을 조정하는 것을 의미합니다. 

살펴본 예제와 같이 추정 값을 변경시킬 수도 있고, 안할수도 있습니다.

이전에 MST의 Prim's 알고리즘에서 가중치와 정점의 key 값을 비교한 것과 같은 방식입니다.

식으로 표현하는 다음과 같습니다.

이상으로 SSP의 개념과 Relax에 대해 알아보았습니다.

Relax는 앞으로 살펴 볼 Bellman-Ford , Dijkstra's 알고리즘의 핵심 개념이므로 기억해주세요.