All-Pairs Shortest Path 알고리즘은 어떻게 방향이없는 대칭 그래프에 최적화 될 수 있습니까?

Question

All-Pairs Shortest Path 알고리즘은 어떻게 방향이없는 대칭 그래프에 최적화 될 수 있습니까?

나는 다른 질문에 대한 오해의 결과로이 질문에 마주 쳤으며 누군가에게 관심이 있다고 생각했습니다.

All-Pairs Shortest Paths가 더 흥미로운 질문 일지 모르지만 중요한 최적화가있는 경우 Single-Source Shortest Path를 자유롭게 언급하십시오.

특히 대칭 그래프에만 집중하지 않는 한 최단 경로 알고리즘 비교를 찾고 있지 않습니다.

Answer 1

더 잘 설명하기 위해 나비의 은유 (날개가 대칭이라고 가정)를 사용하겠습니다.

일반적인 정점 : 대칭 선 (따라서 나비의 본문)을 구성하는 모든 정점.

알고리즘 :

• 대칭 측면 중 하나 (및 연결 가장자리)에 놓여있는 모든 정점

  는 나비의 날개 중 하나를 제거 그래프에서 제거합니다.

• 실행이 새로운 그래프상의 최단 경로 알고리즘

• 그래프는 방향성이며 모든 제거 정점은이 있기 때문에 이제 (에서/다른 모든 정점에서에/모든 일반 정점에 가장 짧은 경로가 이 새로운 그래프의 대칭 버텍스 (공통 버텍스와 동일한 거리를 가짐)

  나비의 몸체와 몸체 사이의 최단 경로는 두 날개 중 어느 한 점을 통과 할 수 있습니다. 이것은 나비의 몸체에있는 어떤 점에서 날개 위의 어떤 지점까지의 거리가 몸체의 해당 지점에서 다른 날개의 같은 지점까지의 거리와 같기 때문입니다. 이는 반대 방향과 같은 거리이기도합니다 이들 중 하나의 경로.

• 이제 각 비 일반 정점 a, 서로가 아닌 일반 정점 b 각 공통의 정점 c를 들어, 우리가 이미 갖고 있기 때문에 cb에 (일정 시간 조작 (단지 추가)에 a의 거리를 기록 a에서 c까지 및 c에서 b까지의 거리).
  대칭 버텍스가 b (또는 대칭 버텍스가 a에서 b) 인 최소 거리는 a에서 모든 공통 버텍스 사이의 최소 거리가됩니다.

  한 날개에서 임의의 지점에서 다른 날개 지점까지의 최단 경로를 결정하기 위해 모든 경로를 첫 번째 점에서 본문의 각 점까지 그리고 몸체의 각 점에서 두 번째 점까지 확인합니다. 그런 거리를 찾아야합니다.