algorithm - 알고리즘 - 임의의 노드 순서를 통과하는 최단 경로 찾기?



graph shortest-path (3)

Dijkstra의 알고리즘을 한 번 호출하여 그래프의 한 꼭지점에서 다른 꼭지점까지의 최단 경로를 얻습니다. 따라서 각각의 고유 한 시작점을 검색하면 반복되는 정점이 문제를 더 어렵게 만들지 않아도됩니다.

이 이전 질문 에서 OP는 u에서 v로 이동하는 그래프에서 최단 경로를 찾는 방법을 물었고 어떤 노드 w를 통과합니다. 허용 된 대답은 Dijkstra의 알고리즘을 두 번 실행하는 것이 었습니다. 한 번은 u에서 w까지, 한 번은 w에서 v까지 가야했습니다. 이것은 Dijkstra 알고리즘에 대한 두 번의 호출과 동일한 시간 복잡도를 가졌습니다.이 알고리즘은 O (m + n log n).

이제 관련 질문을 고려해보십시오. 노드 u 1 , u 2 , ..., u k 의 시퀀스가 ​​주어지며 u 1 에서 u k 까지의 최단 경로를 찾아 경로가 u 1 , u 2 , ..., u k 순서대로. 이것은 인접한 정점의 각 쌍에 하나씩 Dijkstra 알고리즘의 k-1 인스턴스를 실행 한 다음 최단 경로를 연결하여 수행 할 수 있습니다. 이것은 O (km + kn log n) 시간이 걸립니다. 또는 Johnson의 알고리즘과 같은 모든 쌍의 최단 경로 알고리즘을 사용하여 모든 최단 경로를 계산 한 다음 O (mn + n2 log n) 시간에 적절한 최단 경로를 연결하여 k보다 훨씬 큰 k에 유용 할 수 있습니다.

내 질문은 k가 작은 경우 위의 방법보다 빠른이 문제를 해결하기위한 알고리즘이 있는지 여부입니다. 그런 알고리즘이 존재합니까? 아니면 Dijkstra의 iterated it 's good만큼 좋은가요?


Answer #1

나는 우리가 어떻게 더 잘 할 수 있는지 보지 못한다. 내가 생각할 수있는 모든 것이 여기에있다. 그래프가 방향이 없다고 가정하면, 노드 u에서 노드 v까지의 최단 경로는 v에서 u까지의 경로와 동일합니다 (역순으로).

u1 u2 u3 .. un 순서로 최단 경로를 택한 경우, Djikstra의 알고리즘을 u2에서 실행할 수 있습니다. (가장 짧은 경로는 u1-u2, u2-u3를 한 번 실행합니다), u4 (u3 -u4 및 u4-u5), u6 .. 등등. 이렇게하면 Djikstra를 약 절반 정도 적용하는 횟수가 줄어 듭니다. 복잡성이 현저하다는 점에 유의하십시오. 이는 원래의 솔루션과 동일합니다.


Answer #2

한 번에 하나의 경로를 찾기 위해 Dijkstra 알고리즘의 분리 된 인스턴스를 실행하는 대신, 수정 된 Dijkstra와 같은 탐색의 단일 인스턴스가 동시에 시퀀스의 각 노드에서 시작될 수 있습니다 (uj u(k) -> u(k+1) 검색 영역이 "in-the-middle"을 충족시킬 때 경로가 형성됩니다.

이것은 잠재적으로 방문한 총 에지 수를 줄이고 Dijkstra의 알고리즘에 대한 일련의 분리 된 호출을 만드는 것과 비교하여 에지의 재 트래버 설을 줄입니다.

쉬운 예는 두 노드 사이의 경로를 찾는 것입니다. 하나의 노드를 확장하는 것보다 두 노드에 대한 검색 영역을 확장하는 것이 좋습니다. 균일 한 그래프의 경우, 두 번째 옵션은 노드 사이의 거리와 같은 반경을 가진 탐색 영역을 제공합니다. 첫 번째 옵션은 전체 탐색 영역보다 적은 반경의 두 영역을 제공합니다.

그냥 생각.

편집 : 순서 {u(1), u(2), ..., u(m)} 노드가있는 방향과 함께 양방향 검색 의 다 방향 변형에 대해 이야기하고 있다고 생각합니다. {u(1), u(2), ..., u(m)} .





dijkstra