El algoritmo de rutas cortas en pares es un tipo de algoritmo de grafos que es de gran utilidad para analizar grafos de gran tamaño. Este algoritmo analiza y calcula la ruta más corta ponderada entre pares de nodos o vértices que forman parte de un grafo.

A continuación descubriremos cómo funciona este algoritmo, estudiaremos sus principales casos de uso y podremos observar un ejemplo práctico desarrollado para el entorno de Neo4j para comprender de mejor manera cómo ejecutar este algoritmo.

¿Qué es el algoritmo de rutas cortas en pares?

Los grafos son estructuras complejas construidas con diferentes tipos de información y que se resguarda en los nodos que están conectados a otros nodos a través de aristas. Este algoritmo se encarga de determinar la ruta más corta o eficiente entre todos los pares de nodos del grafo. Este algoritmo posee optimizaciones que permite determinar dicha ruta con mayor velocidad que algoritmos similares de detección de rutas cortas.

Puede suceder que algunos de los pares de nodos que conforman el grafo no sean accesibles entre si, por lo que no existe una ruta más corta. De ser así el valor del algoritmo será infinito.

Plain cypher dentro de su estructura no admite el filtrado de valores infinitos por lo que dentro de la plataforma de desarrollo de Neo4j se agregan extensiones que permiten incluir y valorar estos valores. Ahora que conocemos un poco más sobre su funcionamiento, podemos abordar sus principales casos de uso.

Casos de uso del algoritmo de rutas cortas en pares

El algoritmo de ruta más corta en pares puede ser utilizado para detectar fallas de fluidez de conexiones en sistemas complejos. Este puede indicarnos si pares de nodos no son accesibles entre si, para poder modificar los recorridos. Imaginemos por un momento un servicio de transporte público o de recolección de desechos sólidos.

Podemos aplicar dicho algoritmo para determinar las rutas que deben recorrer las unidades que conforman la red de transporte o recolección para verificar que estás se conecten de forma eficiente con diferentes puntos de interés. También puede ser utilizado para estimar rutas de distribución de conexiones en una red de banda ancha y mínima latencia.

Ejemplo de desarrollo

Para comprender de mejor manera el funcionamiento de este poderoso algoritmo, desarrollaremos su ejecución sobre un grafo con un número determinado de vértices y analizaremos sus pares de nodos para encontrar la ruta más corta existente.

En primer lugar debemos construir un modelo de grafo similar al que presentamos a continuación:

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 ejecutamos el algoritmo y este nos ofrece los resultados del análisis

CALL algo.allShortestPaths.stream('cost',{nodeQuery:'Loc',defaultValue:1.0})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance
WHERE algo.isFinite(distance) = true

MATCH (source:Loc) WHERE id(source) = sourceNodeId
MATCH (target:Loc) WHERE id(target) = targetNodeId
WITH source, target, distance WHERE source <> target

RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC
LIMIT 10 Resultados:

Source	Target	Cost
A	F	100
C	F	90
B	F	90
A	E	80
C	E	70
B	E	80
A	B	50
D	F	50
A	C	50
A	D	50

Este cálculo nos permite conocer 10 pares de nodos principales dentro de la estructura del grafo, estimando que el par conformado por F y E es el que se encuentra más lejano.

Esperamos que esta información sea de utilidad para comprender de mejor manera el uso y potencialidades de este importante algoritmo.

Visita más de Grapheverywhere y descubre todo lo que necesitas sobre algoritmos de grafos.