El algoritmo de ruta más corta de fuente única es una especie de algoritmo que se encuentra en las librerías de desarrollo del poderoso Neo4j y forma parte de los algoritmos de grafos más útiles para determinar recorridos eficientes dentro de la estructura de un grafo.

A continuación descubriremos juntos su concepto, los principales casos de uso, restricciones y un ejemplo práctico desarrollado en Neo4j para comprender de mejor manera su funcionalidad.

¿Qué es el algoritmo de ruta más corta de fuente única?

Este importante algoritmo orientado al análisis de grafos orientado a determinar la ruta más corta de fuente única es el que realiza los cálculos necesarios para detectar la ruta más corta de manera ponderada desde un vértice especifico hacia el resto de los nodos que componen la estructura de un grafo.

El también conocido como algoritmo SSSP ha tomado gran relevancia en el desarrollo de modelos que permitan calcular de forma eficiente los recorridos más cortos dentro de un grafo y puede ser complementado con el algoritmo de Dijkstra o algoritmo de rutas más cortas para solucionar modelos de grafos de alta complejidad.

Casos de uso y restricciones principales

El algoritmo de ruta más corta de fuente única esta pensado para detectar dentro de un grafo la ruta más eficiente que se debe recorrer para llegar desde un nodo especifico a otro. Es por esto su funcionalidad es alta, pero reservada a casos específicos donde se requiera de establecimiento de conexiones eficientes con carácter inmediato. Un ejemplo para comprender esto es en un protocolo de enrutamiento de direcciones IP. Las redes conexión utilizan este algoritmo para detectar cambios imprevistos como fallas en enlaces y así proceder a crear una estructura de enrutamiento nueva en cuestión de segundos.

En cuanto a las restricciones, los algoritmos de ruta más corta de fuente única no se implementan en circunstancias en las que debemos incluir pesos o valores negativos en el calculo. Este algoritmo a diferencia del algoritmo Dijkstra asume que agregar a una ruta una relación adicional no puede hacer que la ruta sea más corta.

Ejemplo en Neo4j

Para comprender de mejor manera el cálculo y los resultados que nos entrega este poderoso y veloz algoritmo, realizaremos la ejecución en cypher del algoritmo de ruta más corta de fuente única en un grafo con 6 nodos y diversas relaciones expresadas a través de aristas, para encontrar la ruta más eficiente de un nodo a otro.

En primer lugar construiremos el grafo declarando cada uno de sus nodos y las conexiones existentes entre cada uno de los vértices de la siguiente manera:

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 cálculo del algoritmo como describimos a continuación

MATCH (n:Loc {name:'A'})
CALL algo.shortestPath.deltaStepping.stream(n, 'cost', 3.0)
YIELD nodeId, distance

RETURN algo.asNode(nodeId).name AS destination, distance

Se continúa con la ejecución del algoritmo para obtener los siguientes resultados

MATCH (n:Loc {name:'A'})
CALL algo.shortestPath.deltaStepping(n, 'cost', 3.0, {defaultValue:1.0, write:true, writeProperty:'sssp'})
YIELD nodeCount, loadDuration, evalDuration, writeDuration
RETURN nodeCount, loadDuration, evalDuration, writeDuration

Name	Cost
A	0
B	50
C	50
D	90
E	120
F	160

 

El resultado indicado en la tabla nos dice que partiendo desde a hacia otro nodo el costo de operación es cero, es decir, la ruta más corta, es la que inicia desde ese vértice.

 

Esperamos que esta información sea de utilidad para comprender las funcionalidades de estos importantes algoritmos de grafos.

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