해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다. 해석하면서 정리한 글입니다.

4.7 Shortest paths in dags

앞서 배운 negative cycles의 가능성을 제외한다면, 2가지의 서브 클래스가 있습니다. 1) negative edges가 없는 그래프 2) cycles가 없는 그래프

1번 case는 앞서 다뤘으며, 이제 2번 case에 대해 배워보겠습니다.

single-source shortest-path in DAG

이제 directed acyclic graphs에서 single-source shortest-path 문제가 선형 시간 내에 어떻게 해결될 수 있는지 알아보겠습니다.

이전과 마찬가지로 모든 최단 경로를 순차적으로 포함하는 업데이트 시퀀스를 수행해야 합니다. 그리고 효율성의 핵심으로 DAG는 노드들을 linearized order 할 수 있습니다.

위 그림의 알고리즘을 보겠습니다.
1) DAG를 DFS에 의해 linearize 할 수 있습니다. 2) 정렬된 순서로 노드들을 방문할 수 있습니다. 3) 각 노드들마다 노드의 edge를 update합니다.

위 방식은 positive에만 적용되는 것은 아니며, 이를 적용하면 가장 longest-paths를 찾을 수도 있습니다. 모든 길이에 ‘-‘부호로 뒤집어주면 끝입니다.

Reference

1. Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf