Algoritmo de rutas más cortas

El algoritmo de rutas más cortas es en uno de los módulos de análisis más importantes de los algoritmos de grafos Este se encarga de detectar dentro de un grafo cuál es la ruta más eficiente o el recorrido de menor distancia entre un par de vértices que conforman un grafo. Dentro de esta categoría destaca el conocido algoritmo de Dijkstra por sus propiedades. A continuación conoceremos aspectos fundamentales para entender el funcionamiento de este algoritmo, conoceremos un ejemplo de aplicación para profundizar más al respecto.

¿Qué es el algoritmo de rutas más cortas?

La búsqueda de rutas más cortas y eficientes no es reciente. Este problema posee una larga historia y se considera uno de los principales problemas de los grafos. Desde el siglo XIX se han desarrollado gran cantidad de estudios para determinar de forma eficiente rutas más cortas para diferentes casos de aplicación. El conocido algoritmo de Dijkstra fue desarrollado por el cientifico del mismo nombre en 1956 mientras se proponía encontrar elementos innovadores para las computadoras ARMAC.

Dijkstra necesitaba encontrar un problema y una solución especial para que las personas ajenas al mundo de la informática pudieran comprender su funcionalidad.

Este algoritmo se encarga de estudiar cada una de las conexiones existente entre los vértices que conforman un grafo para determinar la ruta más corta y eficiente. Este algoritmo orientado a estudios de estructuras de grafos se ejecuta en tiempo real y puede ser utilizado en diferentes casos.

ruta

Casos de uso del algoritmo de ruta más corta

El algoritmo de rutas más cortas tiene una importancia sustancial en el proceso de encontrar ubicaciones físicas. Podemos interactuar de forma sencilla con un módulo de este algoritmo en Google Maps, ya que con la ayuda de este algoritmo podemos conocer las rutas más eficientes para llegar de un sitio a otro.

Adicionalmente este algoritmo puede encontrar los grados de separación entre personas conectadas. Esto se evidencia de forma directa en LinkedIn o en Facebook en los que se indican las personas que nos separan con otras en un grafo de conexiones mutuas enumeradas.

Adicionalmente es importante destacar que este algoritmo posee una restricción especifica. El algoritmo de  Dijkstra no admite pesos negativos. El algoritmo asume que agregar una relación a una ruta nunca puede hacer una ruta más corta, una invariante que se violaría con pesos negativos.

Ejemplo en Neo4j

A continuación presentamos un ejemplo práctico desarrollado en los entornos de Neo4j para comprender de mejor manera el funcionamiento del algoritmo.

En primera instancia construimos un grafo de las siguientes características:

MERGE (a:Loc {name:'A'})
MERGE (b:Loc {name:'B'})
MERGE (c:Loc {name:'C'})
MERGE (d:Loc {name:'D'})
MERGE (e:Loc {name:'E'})
MERGE (f:Loc {name:'F'})

MERGE (a)-[:ROAD {cost:50}]->(b)
MERGE (a)-[:ROAD {cost:50}]->(c)
MERGE (a)-[:ROAD {cost:100}]->(d)
MERGE (b)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:40}]->(d)
MERGE (c)-[:ROAD {cost:80}]->(e)
MERGE (d)-[:ROAD {cost:30}]->(e)
MERGE (d)-[:ROAD {cost:80}]->(f)
MERGE (e)-[:ROAD {cost:40}]->(f);

Posteriormente se ejecuta la consulta del algoritmo:

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath.stream(start, end, 'cost')
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost

Se reciben los resultados:

MATCH (start:Loc{name:'A'}), (end:Loc{name:'F'})
CALL algo.shortestPath(start, end, 'cost',{write:true,writeProperty:'sssp'})
YIELD writeMillis,loadMillis,nodeCount, totalCost
RETURN writeMillis,loadMillis,nodeCount,totalCost

Tabla de resultados

NameCost
A0
C50
D90
E120
F160

De los resultados arrojados por el algoritmo podemos conocer que la ruta más corta desde el vértice A al vértice F, posee un recorrido a través de C, D y E con un costo total de 160, siendo esta la ruta más eficiente encontrada.

Esperamos que esta información te sea de utilidad para comprender los algoritmos de rutas más cortas. 

Visita más de Grapheverywhere para conocer todo lo que necesitas saber sobre los algoritmos de grafos.

Share This