¿Cómo funciona pgRouting shortest_path?

Question

Estoy ejecutando la función short_path pero no devolverá filas de líneas a seguir desde el id de origen al id de destino. ¿Hay alguna forma específica de digitalizar mi conjunto de datos? ¿Entiende pgrouting las intersecciones entre líneas? Digitalizé mis líneas una por una conectando las mismas juntas.

Para ser un poco más claro, en mi DB tengo un gid para cada línea, además de un id de origen y destino para esa línea (además de las otras columnas). ¿No debería la función de camino más corto llevarme de un id de fuente aleatoria a un id de objetivo aleatorio?

Espero que mi problema esté claro, pero avíseme si necesita más explicaciones :)

Gracias de antemano. A

Answer 1

El algoritmo de Dijkstra el camino más corto:

"el algoritmo encuentra el camino de menor costo (es decir, el camino más corto) entre ese vértice y todos los demás vértices. También puede utilizarse para encontrar los costos de los trayectos más cortos desde un solo vértice hasta un solo vértice de destino deteniendo el algoritmo una vez que se haya determinado el trayecto más corto hasta el vértice de destino. Por ejemplo, si los vértices del gráfico representan ciudades y los costos de los caminos de borde representan las distancias de conducción entre pares de ciudades conectadas por una carretera directa, el algoritmo de Dijkstra puede utilizarse para encontrar la ruta más corta entre una ciudad y todas las demás ciudades".

http://www.pgrouting.org/docs/1.x/dijkstra.html

Basado en el algoritmo de la Dijkstra:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 2

¿No debería la función de camino más corto llevarme de una identificación de fuente aleatoria a una identificación de objetivo aleatorio?

Sí, el camino_más corto de pgRouting puede ir de un vértice a otro (si hay una conexión válida, por supuesto).

En mi Db tengo un gid para cada línea, además de una identificación de la fuente y el objetivo de esa línea.

¿Cómo asignó las identificaciones de origen y de destino? ¿Utilizó assign_vertex_id()?

Parece que no hay una conexión válida entre los puntos de inicio y final que probaste.

¿Entiende pgrouting las intersecciones entre líneas?

No. Tiene que haber un vértice en la intersección, de lo contrario no será reconocido.

Actualizar:

En este caso, sin embargo, el gid:1 está intersectando al gid:2, pero supongo que un vértice no está creado adecuadamente

¿Así que tienes dos líneas que se cruzan? Necesitas dividirte en la intersección (resultando en cuatro líneas) si quieres ser capaz de girar en esta intersección. De lo contrario, se interpreta como un exceso o defecto de paso.