DAG Relaxation

최단거리

배움의 가장 높은 단계는 가르치는 것이라 합니다. 몰라도 무엇이라도 얘기하고 표현하다 보면 느는 법. 어떻게든 해봅니다.

DAG란?

DAG란 Directed Acyclic Graph를 뜻합니다. 한국말로 번역하면 "방향이 있고, 순환이 없는 그래프"라고 볼 수 있습니다. 노드와 에지로 구성된 그래프에서 내부 순환이 없고 방향이 있다는 뜻입니다. 방향이 있다는 말이 일상적으로 와닿지 않을 것입니다. 컴퓨터에서는 A, B두 노드가 있을 때 A->B만 또는 B->A로만 갈 수 있는 경우 Directed, 양방향으로 원활히 갈 수 있을 때는 Undirected라고 표현합니다. 

Relaxation이란?

DAG Relaxation이라고 했으니까 이제 Relaxation을 이해하면 DAG Relaxation을 이해할 수 있습니다. 원본 자료에서는 최적값을 알고리즘의 한 종류라고 설명하고 있습니다. 어떤 문제에 대해 최적이 아닌 상태에서 시작해 반복적으로 알고리즘을 수행함으로써 최적의 해결책을 찾는 방법이라고 표현하고 있습니다.

그렇다면 DAG Relaxation이란?

어느 정도 눈치를 채셨을 수도 있습니다. DAG에서 Relaxation으로 풀고자 하는 문제는 무엇일까요. 바로 최단거리를 찾는 것입니다. 위 정의를 종합하면, 최초에 최단거리를 모르는 상태에서 알고리즘을 반복수행해 DAG에서 최단거리를 구하는 것이 DAG Relaxation이라고 정의할 수 있습니다.

DAG Relaxation 구현

수업을 들을수록 이산수학과 논리적 사고를 잘해야 한다는 생각이 듭니다. 하지만 그건 나중에 하기로 하고 어쨌든 일단 해봅니다. 수학 공식처럼 이야기하면 이렇습니다. 시작 노드 s로부터 한 노드 v의 거리가 v의 이전 노드 중 하나인 u와 s까지의 거리에 u와 v 간 거리를 더한 값보다 크면 그 거리를 u와 s의 거리에 u, v 간 거리를 더한 값으로 업데이트한다입니다. 이럴 땐 코드가 편합니다.

 if d [v] > d [u] + w(u, v):

    d [v] = d [u] + w(u, v)

그림으로 보면 조금이나마 더 이해가 됩니다. 

위와 같이 표현해 봤습니다. 우리가 최단거리를 계산하고자 하는 노드를 v라고 합시다. v까지 거리를 최초에 무한대로 설정합니다. 그리고 각 u3, u2, u1을 통한 path를 대조하며 최단거리를 구하게 됩니다. 앞에서 말했던 relaxation. 추정에 추정을 계속 반복하는 작업으로 볼 수 있습니다. 이 단계를 계속 반복하게 되면 시작 노드로부터 모든 노드의 최단거리를 구할 수 있습니다. 원 교재의 코드를 적으면 아래와 같습니다.

사실 많은 내용들이 생략되고 뚱 나와서 당황스럽겠지만 어쨌든 그렇습니다.

DAG Relaxation과 Topo Sort

이 부분은 잘 이해하지 못한 내용입니다. DAG Relaxation을 적용하기 위해서 우선 DAG에 Toplogical Sort를 수행합니다. 그 후 Topo order에 맞게 DAG Relaxation을 적용합니다. 원 교재에선 꽤나 길게 나온 내용인데 이해하기 힘들어 일단 뺐습니다. 결과론적으로 Topo sort순서에 relaxation을 수행합니다.

코드는 위와 같습니다.

끝맺으며

오늘도 어떻게든 설명은 해보았습니다. 영어 표현으로 High level에서는 어느 정도 이해가 되는데 확실히 깊이 이해하기는 어려운 부분이 있군요. 그래도 일단 해봅니다