Bi Directional Dijkstra

양방향 dijkstra

문제

음이없는 가장자리 가중치가있는 그래프, 소스 정점 및 대상 vertec t . s 와 t 사이의 가장 짧은 경로를 찾으십시오

그러나 왜 우리는 문제를 해결하기 위해 Dijkstra 알고리즘을 사용하지 않습니까?

0 (E + VLOGV) 은 DIJKSTRA 알고리즘의 최악의 시간 복잡성으로 매우 빠릅니다. 그러나 2 천만 정점과 5 천만 개의 가장자리가있는 그래프의 경우 평균 몇 초 동안 작동합니다. 따라서 우리는 훨씬 더 빨리 무언가가 필요합니다.

양방향 검색의 세부 사항에 들어가기 전에 "6 도의 분리" 개념을 살펴 보겠습니다.

• 1929 년 헝가리 작가 인 Frigyes Karinthy는 처음으로 그의 짧은 이야기 체인에서 "6 도의 분리" 개념을 제안했습니다.
• 6 도의 분리는 세계의 모든 생물과 다른 모든 것이 서로 6 개 이하로 떨어져 있다는 생각입니다.

이제 가장 인기있는 소셜 네트워크 인 Facebook을 살펴 보겠습니다. Facebook의 평범한 사람이 약 100 명의 친구가 있다고 가정합니다. 그런 다음, 우리가 그 사람의 친구들의 친구를 고려한다면, 100*100은 친구의 친구가 될 것입니다. 우리가 "친구의 친구들의 친구"를 고려한다면, 그것은 100 배나 1 백만 명이 될 것입니다. 그리고 우리가 6 번 계속한다면 1 억 명의 사람들이있을 것입니다.

그러나 전 세계 인구는 76 억입니다.

이제 소셜 네트워크에서의 연결을 통해 두 명의 임의인 A와 B 사이의 가장 짧은 경로를 어떻게 찾을 수 있습니까?

양방향 검색을 고려해 봅시다. 그래서 우리는 A의 친구 친구와 B의 친구 친구 친구들의 친구들을 고려할 것입니다. 6 도의 분리의 개념이 사실이라면, A와 친구의 친구들의 친구들과 친구의 친구들의 친구들 사이에 공통된 사람이있을 것입니다. 그러면 우리는 A와 B를 연결하는 가장 짧은 길을 쉽게 찾을 수 있습니다.

우리는 A와 B 모두에 대해 친구의 약 1 백만 명의 친구를 가질 것입니다. 따라서이 경우 총 2 백만 명만 고려할 것입니다.

정상적인 dijkstra의 알고리즘은 A와 B 사이의 가장 짧은 경로를 찾기 위해 소셜 네트워크에서 약 2 억 명의 사람들을보아야합니다.

양방향 검색이란 무엇입니까?

이것에서 우리는 두 개의 동시 검색을 실행합니다. 하나는 초기 상태에서 1 개를 앞뒤로, 하나는 목표에서 뒤로, 두 사람이 중간에서 만날 때 멈 춥니 다.

그래프 g에서 양방향 dijkstra에 대한 의사 코드

• GR 빌드 (역방향 그래프)
• g의 s (source)에서 dijkstra를 시작하고 gr의 t (target)에서 dijkstra를 시작하십시오.
• g와 gr에서 dijkstra 단계 사이를 번갈아 가십시오
• 일부 정점 "V"가 G와 Gr에서 처리되면 중지하십시오.
• S와 T 사이의 가장 짧은 경로를 계산하십시오.

s와 t 사이의 가장 짧은 경로의 계산 : G의 S에서 전방 dijkstra의 거리 추정치가되도록하십시오. 일부 노드 "V"가 G와 Gr에서 처리 된 후, S에서 T에서 T에서 T에서 T에서 T에서 가장 짧은 경로는 g, gr 또는 둘 다 및 d (s, t) = dist [u] + dister [u]로 처리되는 일부 노드 "u"를 통과합니다.