고도를 사용하여 최단 경로를 찾는 그래프 알고리즘

Question

그리드 (X를 기준)를 고려하십시오. 그리드의 각 포인트에는 Z 값이 있습니다. 이제이 그리드에는 지정된 수의 체크 포인트가 있습니다. 표 D에 평점 D가 있다고 가정하십시오.이 값 D는 최대 값 D를 가진 경로를 교차하기 만하면 모든 검사 점에서 다른 점으로 이동할 수 있음을 의미합니다. 경로 길이는 최대 고도 차이로 결정됩니다 그 경로에서 두 개의 연속 된 노드가 사용됩니다. 나는이 길을 갈 경우

1 1 1 1 1 
2 1 3 1 2                
1 2 3 1 2                

: 예를 들어 고도의 그리드를 고려 (X 수단에 갔다, O는 교차하지 않았 음을 의미합니다) :

이

X X X O O 
O O X O O 
O O X X X 

이 경로의 값은 2 것 가장 높은 고도 차이는 1에서 3으로 이동하는 부분이었습니다.

문제는 다음과 같습니다. 어떤 검사 점에서 다른 점으로 이동하는 것을 허용하는 D의 최소값을 찾습니다. 이는 D가 최대가 될 것임을 의미합니다 하나의 검사 점에서 다른 검사 점으로의 경로 길이. 예를 들어

D가 2 인 경우, 즉 내가

이에 대한 효율적인 알고리즘은 무엇인가 (2)의 최대 값을 갖는 내 모든 경로를함으로써 다른 체크 포인트에서 얻을 수 있음을 의미?

Answer 1

이것은 Dijkstra의 알고리즘과 매우 비슷합니다. 노드에서 시작하여 점점 더 멀리있는 모든 노드를 탐색하십시오. 첫 번째 노드 만 노드로 설정하고 S으로 시작하고 나머지 노드에는 거리 무한대로 레이블을 지정하십시오. S으로 이어지는 비경쟁 가장자리를 고려하고 레이블이없는 경우 미개척 노드에 인접하지 않은 노드에 고도 차를 레이블합니다. 최소 거리의 모든 인접 노드를 S에 추가하고 반복하십시오. 가동 시간은 단지 O(E)이어야합니다.

Answer 2

이 그리드 중 하나에 대한 모든 쌍의 최단 경로 솔루션을 요구하는 것 같습니다. Wikipedia는 Floyd-Warshall (O (v^3)) 또는 Johnson의 알고리즘 (O (VE + V^2 log V))이 좋은 선택이라고 제안합니다 (http://en.m.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths). 모서리의 수가 4 * V보다 적기 때문에 Johnson의 알고리즘은 점차 빨라질 것입니다.