지도에서 가장 짧은 경로

Question

MySQL에서 정규화 된 인접력 목록을 사용하여 가중 그래프를 디자인했습니다. 이제 주어진 두 노드 사이에서 가장 짧은 경로를 찾아야합니다.

나는 PHP에서 dijkstra를 사용하려고했지만 그것을 구현할 수 없었습니다 (너무 어렵습니다). 내가 느낀 또 다른 문제는 내가 dijkstra를 사용한다면 모든 노드를 고려해야한다는 것이며, 아마도 큰 그래프에서 매우 비효율적 일 수 있습니다. 그렇다면 위의 문제와 관련된 코드가 있습니까? 누군가 가이 문제를 해결하는 방법을 보여 주면 좋을 것입니다. 나는 거의 일주일 동안 여기에 갇혔습니다. 도와주세요.

Answer 1

이것은 A* 알고리즘의 전형적인 사례처럼 들리지만 DijkStra를 구현할 수 없다면 A*를 이식하는 것을 볼 수 없습니다.

위키 백과에 a*

편집 : 이것은 당신이 한 노드에서 목표로 얻는 비용을 추정하는 좋은 방법이 있다고 가정합니다 (그러나 과대 평가하는 것이 중요합니다).

edit2 : 인접력 목록 표현에 문제가 있습니다. 맵의 각 정점에 대한 객체를 만들면 링크가있을 때 이러한 객체에 직접 연결할 수 있습니다. 따라서 본질적으로 가지고있는 것은 각각에 인접한 노드에 대한 포인터 목록 (또는 참조, 참조)을 포함하는 객체 목록입니다. 이제 새 노드의 경로에 액세스하려면 링크를 따릅니다. 무한 사이클을 피하기 위해 주어진 정점에 대해 따르는 경로 목록을 유지하십시오.

무언가에 액세스해야 할 때마다 DB를 쿼리하는 한, 어쨌든이 작업을 수행해야합니다. 최선의 희망은 필요할 때만 DB를 쿼리하는 것입니다 ... 이것은 그래프의 특정 모서리에 대한 정보를 얻거나 그래프의 하나의 vertext에 대한 모든 가장자리에 대해 쿼리하는 것을 의미합니다 (후자는 아마도 가능성이 있습니다. 더 나은 경로가 되십시오) 그래서 당신은 한 번에 거대한 덩어리보다는 가끔씩 느린 I/O를 한 번만 쳤다.

Answer 2

다음은 Java의 Dijkstra 알고리즘의 문맹 버전입니다. PHP에서 구현하는 방법을 파악하는 데 도움이 될 수 있습니다.

http://en.literateprograms.org/dijkstra%27S_ALGORITHM_%28JAVA%29

Answer 3

dijkstra 알고리즘은 주어진 정점에서 다른 정점으로 가장 짧은 경로를 반환합니다.
의사 코드를 찾을 수 있습니다 위키.

그러나 나는 당신이 필요하다고 생각합니다 플로이드 지시 된 포도에서 모든 정점 사이에 가장 짧은 경로를 찾는 알고리즘.

둘의 수학적 복잡성은 매우 가깝습니다.

나는 찾을 수있다 PHP 구현 둘 다 위키에서.