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

Chapter04. Paths in graphs

4.1 Distances

앞선 시간에 DFS는 지정된 시작점에서 도달할 수 있는 그래프의 모든 정점을 쉽게 식별한다는 것을 배웠습니다. 또한 검색 트리에 요약된 꼭짓점의 명시적 경로도 찾을 수 있습니다. 그러나, 이러한 경로가 가능 economical paths가 아닐 수도 있습니다.

위 그림에서 (a)는 simple graph이며, (b)는 depth-first search tree입니다.

(b)의 DFS 트리에서 C는 S에 도달하기 위해 길이 3의 경로를 표시하지만, (a)의 그래프에서 vertex C는 단순히 하나의 edge만 통과하면 S에 도달할 수 있습니다.

이번 장에선 그래프에서 shortest paths 찾기 위한 알고리즘을 배워보겠습니다.

Path lengths를 이용하면 그래프의 여러 꼭짓점이 서로 떨어진 정도를 정량적으로 설명할 수 있습니다.

두 노드 사이의 거리는 노드 사이의 최단 경로 길이입니다.

위 개념을 physical realization 해보겠습니다.

• vertex S를 고정시키고 나머지를 늘어뜨려 보겠습니다.
• 어떤 특정 점까지의 거리는 S 아래로 걸려있는 거리가 얼마나 인지와 같은걸 알 수 있습니다.
• $dist(B, S) = 2$
  • 2 shortest paths
• 오른쪽 그림은 S를 손으로 올려서 taut하게 만든 그림이며, $edge(D,E)$는 shortest path에 어떤 역할도 없고 그저 slack으로 남습니다.

Reference

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