Algorithm - 22. 최단 경로(3) / DAG

최단 경로 포스팅 3번째는 DAG에서 최단 경로를 찾는 방법을 알아본다. DAG은 Directed Acycle Graph의 준말로 싸이클이 없는 방향그래프를 의미한다.

그래프가 DAG인 경우 다익스트라나 벨만포드 알고리즘보다 더 빠른 속도로 최단 경로를 구할 수 있다. 이전 포스팅에서 DAG을 설명하면서 위상 순서에 대해 언급했다. DAG의 최단 경로 알고리즘은 음의 가중치 간선에 대해서도 정확히 수행하며 별다른 데이터 구조를 사용하지 않고 빠른 속도로 수행한다는 장점이 있다.

DAG 최단 경로 알고리즘 의사코드

Alg DAGShortestPath(s)
	input start vertex s, DAG G
    output label distance(v), is the distance from s to v
    
topological ordering v[1], v[2] ... v[n]	//그래프 위상 순서 계산

for each v in G.vertex() {	//정점 라벨 초기화
	distance(v) <- big number
}

distance(s) <- 0	//출발 정점 라벨 0

for i<-1 to n-1 {	//위상 순서대로 v[i]에 대해서 나가는 간선 기준 작업
	for each e in G.outIncidentEdge(v[i]) {
    	target <- G.opposite(v[i], e)	//간선 완화
        distance(target) <- min(distance(target), distance(v[i]) + weight(e))
    }
}

DAG 최단 경로 그림 수행 예시

먼저 위상 순서를 구해 정점에 번호를 매긴다.

번호의 순서(위상 순서)대로 정점을 뽑고 해당 정점 기준으로 간선 완화 작업을 수행한다.

가장 마지막 순서 n을 하지 않는 이유는 나가는 간선이 존재하지 않기 때문이고 정점을 추출하여 반복 라운드 수행은 1번부터 n-1번까지 한다.

DAG 최단 경로 성능

DAG에서의 최단 경로 알고리즘은 정점을 뽑아서 해당 정점을 기준으로 간선 완화 작업을 한다는 점에서 다익스트라와 매우 유사하다. 그러나 정점을 뽑아내는 순서에 차이가 있다. 다익스트라 알고리즘은 그 때 그 때 정점의 라벨을 보고 최소가 되는 것을 뽑아내고 간선 완화 작업 이후 큐의 정점들을 재정렬한다면, DAG은 최초 위상 순서를 정하여 그 순서대로 뽑아서 쭉 간다.

DAG의 최단 경로 알고리즘은 위상 정렬에 O(V+E)시간, 간선 완화 반복 작업에서 O(V+E) 시간 소요되어 총 O(V+E) 시간에 수행한다.

참고: 국형준. 알고리즘 원리와 응용. 21세기사, 2018.