P가 u와 v 사이의 최단 경로이면 모든 하위 경로도 최단 경로임을 증명하기 쉽습니다. 연결된 그래프 주어 , I는 행렬에서의 전처리 노드의 각 쌍 사이의 최단 거리를 원하는되도록, X 경우경합중인 최단 경로 사전 처리
나는 알고리즘이나 증명을 알아낼 수 없으며 실제로 이것이 가능한지 모릅니다. 모든 아이디어는 환영합니다. 감사합니다.
무향 그래프로 작업하는 경우 또는 모든 호에 대해 호 (a, b)의 무게가 호 (b, a)의 무게와 같을 경우에만 얻을 수 있습니다 (1) 귀하의 그래프에.
문제는 모든 쌍의 최단 경로 문제와 같은 것으로 들립니다. 연결된 그래프의 각 노드 쌍에 대해 노드 쌍 사이의 최단 경로를 찾습니다. Floyd-Warshall 알고리즘은 경로 길이를 찾는 데 사용할 수 있으며 거기에서 가장 짧은 경로를 재구성하는 것은 간단합니다.
이 알고리즘은 부정적인 사이클이 없다는 것을 추가로 요구합니다 (그렇지 않은 경우 짧은 사이클은 항상 해당 사이클을 다시 실행함으로써 얻을 수 있지만 그 요구 사항은 합리적입니다).
속성 (2)을 보장하려면 경로를 재구성 할 때 하나 이상의 최단 경로가 가능할 때마다 "표준"경로를 재구성해야합니다. 이렇게하려면 꼭지점에 순서를 매기고 항상 후보 노드를 오름차순으로 테스트합니다. 최단 경로 특성을 유지하는 최하위 노드를 항상 선호합니다.
위키 피 디아는 상당히 훌륭한 글을 남깁니다.