Vue d’ensemble

Un chemin le plus court entre deux nodes est le chemin qui a le moins d'edges. Les résultats de correspondance de modèle de chemin peuvent être restreints aux chemins les plus courts en utilisant les sélecteurs de plus court chemin suivants :

^[1] k est un entier non négatif. Si moins de k chemins les plus courts existent, tous sont conservés. Lorsque k est omis, il se par défaut à 1.
^[2] Les mots-clés GROUP et GROUPS peuvent être utilisés de manière interchangeable car ils n'affectent pas le résultat.

Les chemins les plus courts sont généralement sélectionnés à partir de l'ensemble des chemins possibles entre deux nodes dans le graph, avec ou sans la contrainte de longueur. Les modèles de chemin quantifiés vous permettent de spécifier une plage de répétitions pour certains segments d'un chemin, facilitant l'exploration de différents chemins possibles.

Sélectionner les chemins "les moins chers", ce qui est analogue aux "plus courts" mais minimise la somme des coûts (poids des edges) le long d'un chemin, n'est pas encore pris en charge dans GQL. Si cette fonctionnalité est requise, vous pouvez envisager d'utiliser les commandes UQL ab() ou autonet() à la place.

Les variables sous-chemin ne sont pas prises en charge dans les chemins les plus courts.

Exemple de Graph

Les exemples suivants s'exécutent sur ce graph :

Pour créer ce graph, exécutez la requête suivante sur un graph vide :

INSERT (zenith:City {_id: "Zenith"}),
       (arcadia:City {_id: "Arcadia"}),
       (verona:City {_id: "Verona"}),
       (nebula:City {_id: "Nebula"}),
       (mirage:City {_id: "Mirage"}),
       (lunaria:City {_id: "Lunaria"}),
       (solara:City {_id: "Solara"}),
       (eldoria:City {_id: "Eldoria"}),
       (nexis:City {_id: "Nexis"}),
       (arcadia)-[:Links]->(zenith),
       (arcadia)-[:Links]->(verona),
       (arcadia)-[:Links]->(solara),
       (mirage)-[:Links]->(arcadia),
       (nebula)-[:Links]->(verona),
       (mirage)-[:Links]->(nebula),
       (verona)-[:Links]->(mirage),
       (mirage)-[:Links]->(eldoria),
       (solara)-[:Links]->(eldoria),
       (lunaria)-[:Links]->(solara)

ALL SHORTEST

Pour obtenir tous les chemins avec la plus courte longueur, utilisez le sélecteur ALL SHORTEST.

MATCH p = ALL SHORTEST (a)-{,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Résultat :

SHORTEST k

Pour obtenir k chemins les plus courts dans chaque partition, utilisez le sélecteur SHORTEST k.

MATCH p = SHORTEST 2 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Résultat :

MATCH p = SHORTEST 3 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Étant donné qu'il n'existe que deux chemins avec la plus courte longueur de 2 entre Arcadia et Eldoria, un chemin avec la deuxième plus courte longueur doit être sélectionné. Dans cet exemple, il n'y a qu'un chemin avec la deuxième plus courte longueur de 3, par conséquent les trois chemins suivants sont retournés :

SHORTEST k GROUP

Pour obtenir les chemins avec les longueurs de 1 à k dans chaque partition, utilisez le sélecteur SHORTEST k GROUP. Le sélecteur groupe les chemins par longueur et trie les groupes par ordre croissant de longueur, puis sélectionne tous les chemins dans les premiers k groupes.

MATCH p = SHORTEST 3 GROUP (a:City)-[]-+(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Deux chemins avec la plus courte longueur de 2, un chemin avec une deuxième plus courte longueur de 3 et un chemin avec une troisième plus courte longueur de 4 sont retournés :

Partitions

Lorsqu'un modèle de chemin correspond à plusieurs nodes de départ et nodes d'arrivée, les résultats de la correspondance sont conceptuellement partitionnés par les paires distinctes de nodes de départ et d'arrivée. La sélection des chemins les plus courts est ensuite effectuée au sein de chaque partition.

Dans cette requête, le produit cartésien de a et b est généré avant d'être référencé dans le modèle de chemin le plus court, donc quatre chemins les plus courts sont sélectionnés au total parmi les quatre partitions :

MMATCH p = SHORTEST 1 (a:City WHERE a._id = 'Zenith' OR a._id = 'Arcadia')-{,10}(b:City WHERE b._id = 'Eldoria' OR b._id = 'Nebula')
RETURN p

Résultat :

Chemins les Plus Courts à Source Unique

Cette requête obtient un chemin le plus court entre Arcadia et chaque autre ville :

MATCH p = SHORTEST 1 (c1:City {_id: 'Arcadia'})-{,10}(c2:City)
WHERE c2._id <> c1._id
RETURN p

Il y a 7 villes qu'Arcadia peut atteindre dans le graph, tandis que Nexis n'est pas atteignable. Voici un des retours possibles :