La ruta más corta en un mapa

Question

He diseñado un grafo ponderado utilizando una normalizado de la lista de adyacencia en mysql.Ahora necesito encontrar el camino más corto entre dos nodos.

He tratado de usar Dijkstra en php pero yo podía manejar para su implementación (demasiado difícil para mí).Otro problema que yo sentí fue que si yo uso Dijkstra sería necesario tener en cuenta todos los nodos, que puede ser muy ineficiente en un gran gráfico.Así que ¿alguien tiene un código relacionado con el problema anterior?Sería genial si alguien al menos me muestra una manera de resolver este problema.He sido atrapado aquí por casi una semana.Por favor, ayudar.

Answer 1

Esto suena como un caso clásico de Un* algoritmo, pero si no se puede implementar de Dijkstra, te veo implenting Un*.

Un* en la Wikipedia

editar:esto supone que usted tiene una buena forma de estimar (pero es crucial que no sobre-estimar) el costo de llegar de un nodo a la meta.

edit2:usted está teniendo problemas con la lista de adyacencia de la representación.Se me ocurre que si se crea un objeto para cada vértice en el mapa, a continuación, usted puede ir directamente a estos objetos cuando hay un vínculo.Entonces, lo que tendríamos es esencialmente una lista de objetos que contienen cada uno una lista de punteros de referencias (o, si se quiere) a los nodos son adyacentes.Ahora, si quieres acceder a la ruta de acceso para un nuevo nodo, sólo tienes que seguir los enlaces.Asegúrese de mantener una lista de los caminos que he seguido para un determinado vértice para evitar ciclos infinitos.

Tan lejos como la consulta de la base de datos cada vez que usted necesita para tener acceso a algo, vas a tener que hacer esto de todos modos.Su mejor esperanza es sólo una consulta a la DB cuando se NECESITA...esto significa que sólo consultar cuando lo desee para obtener información sobre un borde en el gráfico, o para todos los bordes para una vertext en el gráfico (el último, es probable que sea la mejor ruta), por lo que sólo llegará a la e/S lento de vez en cuando en lugar de gigantescos trozos de todos a la vez.

Answer 2

Esta es una versión de leer y escribir el algoritmo de Dijkstra, en Java, que puede ayudar a averiguar cómo ponerlo en práctica en PHP.

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

Answer 3

devuelve el algoritmo de Dijkstra rutas más cortas desde el vértice dado a otros vértices.
Puede encontrar su pseudo-código en Wiki .

Sin embargo, creo que es necesario Floyd algoritmo que encuentra caminos más cortos entre todos los vértices en un grapth DIRIGIDO.

La complejidad matemática de ambos son bastante cerca.

aplicación PHP de la Wiki para los dos.