여러 지역 사이의 최단 거리를 표시/얻을 수있는 가장 좋은 방법을 알아 내려고 노력하고 있어요 MySQL의 DB

Question

에서 PHP를 통해 두 개의 "위치"사이의 최단 경로를 계산. 가장 잘 설명하려면지도로 생각하고 아래에서 다음을 사용하십시오. 각 위치의 모든 거리와 경로는 이미 mysql 데이터베이스에 저장됩니다.

위치 (편지 -. []에> 위치가 도달 할 수있는 거리/시간)

A -> B [5] 
A -> C [4] 
B -> Z [1] 
C -> Z [50] 

그래서 A는 B로 이동 5 분 거리에 있습니다. A에서 C로가는 데는 4 분이 걸립니다.

이제 내가 알아 내려고하는 것은 누군가가 현재 위치 A에 있고 Z에 가길 원한다고 말하면서 어떻게 시스템이 데이터베이스를 통과하여 A -> B - > Z가 가장 짧은 경로가 비교입니다 -> C -> Z.

내가 원래 각 시스템에 루프를하고 생각했지만,이 설정은 다른 위치 및 경로의 수백을 포함하는 것입니다. 그래서 나는 이미 무한 루프를 만드는 것을 볼 수 있습니다. 두 번째는 시작 위치로 되돌아가는 경로를 따르는 것입니다.

은 아마 롤 불가능하다.

은 어떤 도움이나 제안은 많이 주시면 감사하겠습니다!

고맙습니다.

Answer 1

Shortest Path Problem 수많은 알고리즘으로 해결 될 수있다. Dijkstra은 고전입니다.

1. 모든 노드에 거리 값을 할당하십시오. 초기 노드에서는 0으로 설정하고 다른 모든 노드에서는 무한대로 설정하십시오.
2. 모든 노드를 방문하지 않은 것으로 표시하십시오. 초기 노드를 현재로 설정합니다.
는 현재 노드의 경우, 모든 방문하지 않은 이웃을 고려하고 (초기 노드에서) 자신의 임시 거리를 계산한다. 예를 들어, 현재 노드 (A)의 거리가 6이고 다른 노드 (B)를 연결하는 가장자리가 2이면 A를 통한 B까지의 거리는 6 + 2 = 8이됩니다. 이 거리가 이전에 기록 된 거리 (초기 무한대, 초기 노드의 경우 0)보다 작 으면 거리를 덮어 씁니다.
4. 현재 노드의 모든 이웃을 고려한 후에 방문한 것으로 표시하십시오. 방문한 노드는 다시 검사되지 않습니다. 현재 기록 된 거리는 최종적이고 최소한입니다.
5. 모든 노드를 방문한 경우 마칩니다. 그렇지 않은 경우 방문하지 않은 노드를 첫 번째 노드에서 다음 "현재 노드"로 설정하고 3 단계부터 계속하십시오.