Bidirectional Dijkstra 설명

출처 : https://www.coursera.org/learn/algorithms-on-graphs

Bidirectional Dijkstra

Dijkstra Revisited

• Invariant
  • Process한 (heap에서 꺼낸) v까지의 dist는 shortest path의 dist.
• Work toward
  • 모든 v를 방문

Bidirectional Dijkstra Algorithm

• s에서 정방향으로, t에서 역방향으로 탐색하다가 공통으로 process한 m을 만나면 중단.
• 양쪽 다 dist 계산을 한 vertices를 보면서 dist_F(v) + dist_B(v)가 min인 값이 OPT.

Lemma

• BiDijkstra가 m에서 만나면, BiDijkstra가 방문한 vertices로만 구성된 shortest path가 존재한다.
• BiDijkstra가 만났을 때, shortest path s->v->w->t가 {s, v} \in F, {w, t} \in B 이면 dist_B(v)는 v->t의 최단거리이다.

응용

• Road network에서는 around 2x faster.
  • v가 촘촘하기 때문.
• Social network에서는 훨씬 더 빠름.
  • v당 e가 100개가 넘고, "6 handshakes"가 적용되기 때문.