6.006: Bellman-Ford 알고리즘의 핵심

Negative Graph

안녕하세요 여러분. 제 오랜 불찰로 글이 너무나 뜸했습니다. 어떻게든 해보려 노력하는데 쉽지 않군요. 하지만 포기할  수 없습니다. 분명 지금 해내지 못하면 다음에 후회할 것입니다. 그래도 공부한 내용을 적어보도록 하겠습니다.

12강은 지옥이다

어느 레딧에서도 이야기했듯, 6006은 가끔 너무나 어렵게 이야기를 전개한다고 합니다. 사실 제가 부족한 부분도 많습니다. 특히, 수학적 귀납법을 이용해 문제를 증명하는데 이 부분이 거의 이해가 가지 않습니다. 따라서, 수학적 귀납법을 배운 후에 내용을 본다면 수업을 듣기 비교적 수월하실 것입니다. 이해하지 못하는 많은 내용들은 일단 제쳐두고 진행해 보도록 하겠습니다.

Bellman-Ford 알고리즘의 아이디어

지난 DAG Relaxation에서는 Directed이며 Cycle이 없고, Negative weight가 없는 경우에만 가능했습니다. 하지만 Bellman-ford에서는 Undirected Negative에서도 가능하다는 장점이 있습니다. 이를 위한 아이디어를 위해 다음 두 가지 과정을 거칩니다

1. 그래프 복제

그래프를 복제한다는 표현이 다소 어색합니다. 결과를 놓고 보면 "그래프를 흩뿌린다"라는 표현이 더 어울려 보입니다. 설명을 해보면 이렇습니다. 각, 노드를 시작점으로 했을 때를 0이라고 하고 하나의 열에 놓습니다. 그다음 열을 하나 만들고 이를 1 열이라 합니다. 1열에도 마찬가지로 모든 노드를 놓습니다. 대신 0열의 각 노드에서 1열의 각 노드로 연결할 때, 기존 그래프의 연결관계를 그대로 표시합니다. 가령 원본 그래프에서 a노드가 있고 b노드가 있다고 해봅시다. a를 기준으로 b로는 연결되어 있고, b에서 a로 연결되어 있지 않은 상태입니다. 그렇다면 0열에는 a, b를 그대로 놓습니다. 1열을 그릴 때 a, b를 우선 그립니다. 주어진 조건에서 a에서 b로 연결되어 있다고 했으니 0열의 a(a_0)에서 1열의 b(b_1)는 선 그어 줍니다. 이게 핵심입니다. 

위 설명을 기준으로 왼쪽 위 그래프와 오른쪽의 "복제된 그래프" 관계를 이해하셨다면 그래프 복제는 이해한 것입니다. 왼쪽밑 표는요? 저도 좀 더 알아보겠습니다.

2. DAG Relaxation 수행

그다음엔 DAG Relaxation을 수행합니다. 음... 그 저번에 모든 거리를 무한대로 해 놓은 후 했던 것 같은데.... 아무튼 기억을 더듬어보면 이렇습니다. DAG에서는 모든 노드의 위치를 양의 무한대 위치에 놓았습니다. 그런 후, 노드 방문 시 이전 노드까지의 거리 + Weight가 현재 노드의 거리보다 작으면 해당 값으로 업데이트되는 방식이었습니다. 

Bellman-Ford에서 쓰는 DAG도 이와 유사합니다. 단 여기에 음수 가중치 사이클이 존재하는 경우만 조심하면 됩니다. 판별하는 아이디어는 간단합니다. 레벨 |V|-1에 있는 노드까지의 최단 거리를 delta(s_0, v_(|V|-1))라고 합니다. 그리고 레벨 |V|에 있는 노드까지의 최단 거리를 delta(s_0, v_|V|)라고 합니다. 논리적으로 생각하면 다음 레벨까지 거리는 이전 레벨까지 거리보다 커야 합니다. 하지만 만약 작다면? 음수인 Weigh가 존재하는 것입니다.

위 내용을 제대로 증명하려면 꽤나 복잡한데, 사실 저도 아직 이해를 못 해 그 부분은 넘어가도록 하겠습니다.

끝맺으며

오늘은 굵직한 부분만 정리해서 올렸습니다. 뒤에 시간 복잡도 등등의 내용등이 있는데, 위에서 설명한 내용과 좀 더 현실적인 코드내용은 달라 시간 복잡도는 다른 것으로 보입니다. 해당 내용은 좀 더 공부를 해서 올려보도록 하겠습니다.