Bonjour à tous,

J'ai un souci avec la performance d'une requête de calcul de chemin le plus court.

Tout d'abord, je vous expose le contexte : je souhaite modéliser un graphe orienté multiple. Voila pour la théorie.
Dans la pratique, cela peut s'apparenter à un GPS. J'ai une liste de sommets (les villes) et des arêtes (les routes). Mes routes sont unidirectionnelles et ont une longueur. Il existe des boucles. De plus il existe aussi des villes reliées entre elles par deux routes distinctes (mais n'ayant pas la même longueur).

Je connais la ville de départ de toutes mes excursions et je cherche a rallier mon point d'arrivée qui est connu à l'avance. Mais attention, je dois impérativement passer par certaines 'routes' et je ne reviens jamais au point de départ (ce n'est pas un cycle)

Voici un exemple de graphe que je modélise :

(Je n'ai pas pu représenter les routes multiples)

Pour modéliser tout cela, j'ai deux tables fixes : la table des villes et la table des routes. Une route a une ville de départ, une ville d'arrivée et une longueur
J'ai par ailleurs une table dynamique qui contient une ligne par passage dans une route

Ma technique utilisée pour résoudre le problème :
Je calcule l'ensemble des chemins possibles entre la ville de départ et la ville d'arrivée. Avant de partir, je calcule la liste des chemins qui passent par toutes les routes qui m’intéressent et je prend le plus court.
Je me suis aidé de l'excellent papier sur les requêtes récursives http://sqlpro.developpez.com/cours/s...te-recursives/.

Dans ma base j'ai 32 villes et 60 routes.

Le problème est que depuis le point de départ de mon périple vers la dernière ville me donne presque 70 000 possibilités de chemins (en presque 3 minutes).

Or maintenant on me demande d'effectuer le calcul en temps réel (cad en moins d'environ 100ms) et cela pour n'importe quel point.
En gros une fois que j'arrive dans une ville, je dois recalculer le chemin le plus court pour aller vers la dernière ville, tout en passant par les routes obligatoires et en éliminant celles déjà visitées.

La requête récursive me donne une liste de chemins possibles. Chaque chemin comporte un varchar avec les routes empruntées séparées par une virgule. Si je décompose cette liste en lignes pour faciliter la comparaison avec les routes obligatoires, j’obtiens une liste de prés de 2milions de lignes, ce qui est incompatible avec ma performance.

Pouvez vous m'aider sur la méthode employée ? Trouvez vous la technique viable ou bien dois je repenser la structure pour améliorer la performance ?

Si vous le souhaitez je peux donner des définitions de tables et les requêtes utilisées pour générer tout cela.

Merci d'avance !

(Désolé pour la longueur)