인생은 여행, 즐기며 살렵니다

(앞의 (상) 에 해당하는 글을 보지 못하신 분은, 먼저 보고 오시면 좋겠습니다.) (다시 한 번 적습니다만, 이 책은 [알고리즘 문제 해결 전략] 의 책 내용을 정리한 것입니다,) 저번 글에서는, u에서 v까지 가는 경로 중에, S의 원소를 경유점으로 사용하는 최단 경로의 길이는 [1번 식] 로 나타나짐을 살펴보았다. 이제 이 식을 점화식 형태로 나타내기 위해서, 형태를 살짝 바꾸어 보자. 그래프의 노드의 개수가 V개라면, 각각의 노드들을 0부터 V-1 까지 번호를 붙일 수 있다. 인 원소 k에 대해서, 이라 하자. 다른 말로 하면, 는 0부터 k까지의 정수를 원소로 갖는 집합이다. 이렇게 표현하는 경우, 는 0부터 k까지의 노드의 집합이 되며, 우리가 구하고자 하는 u에서 v까지의 최단 거리는, '모..

플로이드의 모든 쌍 최단 거리 알고리즘 (이 내용은 '알고리즘 문제 해결 전략' 의 내용을 정리한 것입니다.) 1. 플로이드의 최단 쌍 알고리즘의 기본적인 개념 그래프 내의 어떤 두 점을 u와 v라고 할 때, u에서 v로 가는 경로가 있다고 하자. 이 두 점을 잇는 경로는, u와 v를 직접적으로 연결하는 하나의 간선일 수도 있고, 아니면 다른 점들을 거쳐서 가는 경로일 수도 있다. 후자의 경우, 예를 들면 u - a - b - c - v 와 같은 형태가 될 것이다. 이렇게 u에서 v로 가는 경로가 다른 점을 경유해서 가는 경우, 이 경유하는 점들을 경유점이라 하자. 즉, 위에 예로 든 경로에서는 a, b, c가 경유점이 된다. 정점 집합 S에 포함된 정점만을 경유점으로 사용해서, u에서 v로 가는 최단 ..