목차

최단 경로 (Shortest Path Problem)
토론

최단 경로 (Shortest Path Problem)

크게 두 종류의 문제 유형이 있다.
- 단일 출발지 최단 경로
- 모든 쌍 최단 경로
사실 이보다도 흔히 나오는 것은 특정 쌍 최단 경로인데, 이것은 보통 단일 출발지 최단 경로 알고리즘으로 처리한다.
- 기본적으로는 그냥 단일 출발지 최단 경로를 돌리다가 특정 목적지에 대해서 최단경로가 구해지면 멈추는 식으로 구현한다
- 양방향 탐색기법을 사용해서, 양쪽에서 패러럴하게 단일 출발지 최단 경로 알고리즘을 돌려서 중간에서 만날때까지 돌리면 조금 더 빨라진다
공통적으로 적용되는 아이디어는
- 최단경로를 이루는 부분 경로들도 최단경로이다
- Edge Relaxation
  - 엣지 (u,v)에 대해서, 기존의 알고있는 v까지의 최단거리 D(v)보다, u를 거쳐서 가는 최단거리 D(u)+w(u,v)가 더 짧으면, D(v)를 D(u)+w(u,v)로 업데이트 해줄 수 있다.

기본적인 문제 유형

다른 그래프 문제들에 비해서, 최단 경로 알고리즘으로 풀어야 하는 문제들은 이 문제가 최단 경로 문제라는 것을 파악하기가 어렵지 않은 편이고, 문제 요구사항에 맞춰서 그래프 모델링을 하는 데에도 별로 어려운점이 없는 편이다
- 전혀 연관 없어 보이는 문제를 기상천외한 방법으로 그래프로 모델링해서 푸는 최대 유량 문제들에 비하면 천사수준이다.
- 가장 단순한 최단경로를 구하라는 문제를 그나마 좀 복잡하게 꼬아놓은 게 간선 이어가기 2 정도이다.

최단 거리를 구한 뒤에, 엣지 웨이트가 변하는 경우

웨이트가 작아지면, 그냥 기존 엣지에 추가로 새로운 엣지가 생긴 것이라고 생각해도 상관 없다. 그 엣지를 이용해서 모든 쌍에 대해서 relaxation을 진행해주면 된다.
웨이트가 커지면 갱신이 쉽지 않다. 오프라인 쿼리로, 웨이트가 작아지는 방향으로 역으로 바꿔서 처리할 수 있다면 그렇게 하자.
관련 문제 31268

앞선 경로에 따라 엣지 웨이트가 다른 경우?

w(u,v)가 u까지 오는 경로에 따라서 달라지는 경우.
u까지 더 짧은 거리로 왔을때 w(u,v)도 더 작아진다면, 가장 짧은 경로의 거리를 이용해서 그대로 D(v)를 구해줘도 최적이다.
- u까지 오는 경로들의 각각 거리가 D1(u), D2(u) 일때, D1(u) + w1(u,v) ≤ D2(u) + w2(u,v) 이면 된다.
관련 문제: 국왕의 방문