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

4.3 Lengths on edges

앞선 예에서 BFS는 모든 edge들을 동일한 길이로 취급했지만, 앞선 사례는 굉장히 드문 상황입니다. 실제로 최단 경로를 찾아야하는 application에는 거의 적용되지 않습니다.

위의 그림은 San Francisco 에서 Las Vegas로 가는 가장 빠른 길을 찾고 싶은 상황을 나타냅니다.

이와 같은 경우를 고려해서, 모든 edge $e ∈ E$에 대해서 $l_e$라는 길이를 갖고 있다고 annotate합니다. $l(u,v)$ 나 $l_{uv}$라고 표현하기도 합니다.

그리고 $l_e$가 항상 물리적인 길이를 표현할 필요는 없습니다. time, money와 같은 어떤 quantity가 될 수도 있습니다. 또한 negative length도 가능합니다.

Reference

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