[알고리즘] Dynamic Programming(동적 계획법)-DAG(Directed Acyclic Graph) shortest path(최단 경로)

위의 그림은 DAG(Directed Acyclic Graph) 이다. DAG는 비순환 그래프를 의미하는데 단순히 말해서 cycle이 존재하지 않는다는 뜻이다. 다음에 그래프의 종류에 대해서는 따로 글을 써보도록 하겠다.

모모든 DAG 그래프는 아래와 같이 linearization 할 수 있다. 

dist(X)가 S로부터 어떤 점 X로 갈때의 최단 거리를 리턴하는 함수라고 생각해보자.

dist(X)를 계산하기 위해서는 dist(C)+3과 dist(B)+1 만 비교하면 된다. 왜냐하면 B와 C만 D의 predecessor 이기 때문이다. Predecessor는 뭐냐면 Q->W 일때 Q를 predecessor, W를 successor 라고 한다. 즉 D 직전에 오는 것이 B와 C밖에 없다는 의미이다.

따라서 임의의 점 X까지의 최단 거리 dist(X)를 구하기 위해서는 X의 predecessor를 반드시 지나야 하므로 dist(X_predecessor)+E(X_predecessor, X)끼리만 비교하면 된다는 것이다!

dist(D)=min{dist(B)+1, dist(C)+3} 이라는 것이다.

또한, DAG에서는 linearization이 항상 가능하므로(나중에 다룰 것이다 직관적으로도 이해하기는 어렵지 않을 것이다.)

맨 왼쪽 점부터 맨 오른쪽 점까지 순서대로 dist를 구하면, 그 값이 모두 최단 거리라는 것을 알 수 있다!

(X의 predecessor가 X의 왼쪽에만 존재하고, 오른쪽에는 존재하지 않기때문에 가능한것이다)

따라서 이 문제를 동적계획법을 이용해서 쉽게 풀 수 있다는 사실을 알 수 있다.

다음은 python을 이용해 시작점으로부터 각 점까지의 최단 거리를 구하는 함수를 Top-down 방식으로 구현한 것이다.