Brevet FR2855287A1 — publié le 20041126

i PROCEDE DE CALCUL DU PLUS COURT CHEMIN DANS UN GRAPHE La présente invention se rapporte au domaine des graphes. La présente invention se rapporte plus particulièrement à un procédé de 5 calcul du plus court chemin dans un graphe valué. Ce type de calcul possède de très nombreux domaines d'applications, comme par exemple les réseaux de télécommunications, le trafic routier... L'art antérieur connaît déjà l'algorithme de Dijkstra. Cet algorithme tient à jour un ensemble X de sommets dont les distances les plus courtes à l'origine sont déjà 10 connues. Au départ, X contient uniquement le sommet correspondant à l'origine. A chaque étape, on ajoute à X l'un des sommets restants dont la distance à l'origine est la plus courte possible. Si tous les arcs ont des étiquettes positives ou nulles, i est toujours possible de trouver un chemin minimal depuis l'origine vers un sommet s ne passant que par des sommets déjà présents dans X. Appelons raccourdci un 15 tel chemin. A chaque étape de l'algorithme, on utilise un tableau D contenant la longueur du meilleur raccourci pour se rendre à chaque sommet. Dès qu'un sommet est atteint, le tableau D contient la distance la plus courte entre l'origine et ce sommet. Pour reconstruire le plus court chemin qui réalise cette distance, il convient alors de tenir à jour un autre tableau C de sommets tel que C(s) contienne le 20 sommet précédant immédiatement le sommet s dans le plus court chemin. L'art antérieur connaît déjà, par la demande de brevet américain US 6 356 911 (IBM) un système de recherche du plus court chemin. Un procédé et un système efficaces sont présentés. Ils permettent de rechercher les plus courts chemins entre une source et des destinations multiples, et entre des sources 25 multiples et des destinations multiples. La vitesse du procédé classique de Dijkstra, qui est le procédé de calcul basique, est amélioré en utilisant des informations sur les relations entre un noeud et un ensemble de destinations dans un graphe. Les informations de relation sont constituées par la fonction d'estimation h(v) concernant un noeud spécifique v et un ensemble T de destinations, o h(v) 30 est une borne inférieure de l'ensemble des longueurs de chemins les plus courts s'étendant du noeud v à chacun des ensembles de destinations T. L'utilisation de la fonction d'estimation peut améliorer la vitesse du procédé de Dijkstra. L'art antérieur connaît également, par la demande de brevet américain U S 2002/0107711 (Sun Microsystems) une recherche du court chemin utilisant des 35 tuiles et une propagation de coût linéaire par pièce. Un procédé pour trouver les plus courts chemins est décrit. Ce procédé utilise un modèle de coût linéaire par pièce pour guider la recherche à travers le graphe de tuiles compact et pour être sûr qu'un plus court chemin peut toujours être trouvé par calcul d'une manière efficace. La fonction de propagation de segment de tuile à segment de tuile est utilisée pour chercher un emplacement cible depuis un emplacement source à travers une région, et le plus court chemin est trouvé en effectuant un retour en arrière en utilisant les fonctions de coût calculées pendant la recherche. La 5 convolution linéaire minimale est utilisée pour faciliter la propagation de la fonction de coût. L'art antérieur connaît également, par la demande de brevet américain US 2001/0032272 (NEC) un routage de plus court chemin basé sur la QoS (Qualité de Service) pour un réseau de communication hiérarchique. Un routeur a une table 10 de topologie de réseau et un nombre de tables de ressource correspondant à des zones du réseau. En réponse à une requête d'un utilisateur, une des entrées de la table de topologie et l'une des tables de ressources sont référencées, une zone traversable le long de la route de destination et des liens de la zone qui satisfont une valeur de QoS spécifiée par l'utilisateur sont sélectionnés. Un calcul est 15 effectué sur les liens sélectionnés, ce calcul étant conforme à l'algorithme de Dijkstra, pour trouver un chemin le plus court vers la destination si l'entrée référencée indique que la destination est dans la zone locale du routeur. Si l'entrée ne l'indique pas, le calcul est poursuivi jusqu'à ce qu'un arbre de chemin le plus court soit trouvé pour tous les routeurs en bordure de la zone traversable ou jusqu'à ce que le calcul se 20 termine si l'arbre n'est pas trouvé pour tous les routeurs, et une route ayant une valeur de QoS optimum est déterminée à partir de l'arbre de plus court chemin. Les procédés connus de l'art antérieur possèdent dans le meilleur des cas une complexité en O(E*ln(V)) o V est le nombre de sommets et E est le 25 nombre d'arêtes. La présente invention entend remédier aux inconvénients de l'art antérieur en proposant un procédé de calcul du plus court chemin dans un graphe qui possède en moyenne une complexité en O(iln(v)) o v est le nombre de 30 sommets et la longueur moyenne du chemin. A cet effet, la présente invention concerne dans son acception la plus générale un procédé de calcul des plus courts chemins en terme de coût et de nombre d'arêtes dans un graphe valué comportant des sommets et une matrice 35 d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur caractérisé en ce qu'il comporte les étapes consistant à * se ramener à des valuations entières non nulles; * éventuellement, se ramener au cas de valuations toutes égales à 1 en créant des sommets intermédiaires entre deux sommets reliés par un arc de valuation strictement supérieure à 1; * effectuer une série d'incrémentations, une incrémentation consistant à 5 trouver l'ensemble des sommets auxquels on peut arriver en partant d'un n-uplet de sommets donné; * effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un nuplet de sommets donné; * les incrémentations et les décrémentations pouvant se succéder dans n'importe quel ordre; * transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na; * sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble de chemins E1; * effectuer Nb = Na + 1; * effectuer tant que (Nb ≤ v(C)) les étapes suivantes de manière itérative: { examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieure à v(C) et sélectionner parmi 25 ceux-ci ceux C' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) C=C'et Nb= Nb+ 1 * les chemins les plus courts en terme de coût étant constitués par le nuplet C. De préférence, le procédé comporte en outre l'étape consistant à effectuer des raffinements successifs du chemin dit "chemin trivial " de longueur Nb, ce 35 chemin étant le chemin qui emprunte Nb fois l'unique arête du graphe G1, le graphe G1, obtenu à partir de GO en effectuant des épaississements successifs, ne comportant qu'un seul sommet et une seule arête. Avantageusement, le procédé comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe GO jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement du graphe G consistant à * munir le graphe G d'une relation d'équivalence; * considérer que les classes d'équivalence sont les sommets du graphe épaissi G';' * étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe sl appartenant à S1 et s2 10 appartenant à S2 tels que sl et s2 sont reliés par une arête dans G; * lavaluation de l'arête S1-S2 de G'étant le minimum des valuations des arêtes sl-s2 de G, avec sl appartenant à S1 et s2 appartenant à S2. Selon une variante particulière, * la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb * on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée. Selon une variante particulière, * la série d'incrémentations s'effectue dans un épaississement du graphe initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur 25 Nb; * on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe; * on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe; * s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape précédente. on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé. Selon un mode de mise en oeuvre particulier, le procédé est appliqué au routage de paquets dans un réseau de télécommunications. Selon une variante, le procédé est appliqué au routage d'appels dans un réseau de télécommunications. Selon une autre variante, le procédé est appliqué à un système de navigation. Selon un mode de mise en oeuvre particulier, le procédé est appliqué à un système de réservation. Enfin, selon une dernière variante, le procédé est appliqué à un système automatisé d'aide à la traduction. L'invention se rapporte également à un système pour la mise en oeuvre du procédé comprenant au moins un processeur et des ressources mémoire. On comprendra mieux l'invention à l'aide de la description, faite ciaprès à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux 15 figures annexées: * la figure 1 représente un graphe GO; * la figure 2 représente un graphe G1 qui est un épaississement du graphe GO; * la figure 3 représente un graphe G2 qui est un épaississement du 20 graphe G1; et * la figure 4 représente un graphe G3 qui est un épaississement du graphe G2. Nous allons, dans un premier temps, donner une nouvelle description du 25 graphe. Ensuite, dans un second temps, nous expliquerons comment cette description peut être utilisée et nous présenterons le procédé selon l'invention, dans différents modes de réalisation. Un graphe non valué est un ensemble (V, E) o V est un ensemble fini, 30 I'ensemble des sommets, et E est un ensemble de couples de sommets. Les éléments de E sont appelés les arêtes. Le premier élément d'une arête est appelé l'origine de l'arête. Son second élément est appelé extrémité. Si (vl,v2) E E= (v2,vl) e E alors on dit que le graphe est non dirigé et E peut être considéré comme un ensemble de paires de sommets. Un chemin entre deux sommets vi et v2 est une suite uo, ... uk d'éléments de V tels que uo= vy, Uk= v2 et pour tout i entier dans [0, k-1], (ui,ui+l) E E Dans ce cas, on dit que kest la longueur du chemin. Le problème du chemin est de trouver le plus court chemin entre deux sommets du graphe, c'est-à-dire dans ce cas le chemin, ou les chemin, utilisant le moins de sommets possible. Un graphe valué est un couple (V, E) o V est un ensemble fini, et E un ensemble de triplets (v, v, x) o (v,v') E Vet x E R vet v'sont les arêtes et xest le coûtou la longueurde l'arête. Un chemin entre deux sommets vl et v2 est une séquence Uo, ... uk d'éléments de V tels que uo= v1, Uk= v2 et pour tout i entier dans [0, k1l], 3 xi E R, (ui,ui+l,xi) E. La longueur du chemin est dans ce cas: k-I i=o Le problème est également de trouver le chemin le plus court entre deux sommets. Dans le domaine des graphes, il est courant d'utiliser des matrices 25 d'adjacence, c'est à dire des matrices représentant l'ensemble des coûts des arêtes sortantes et des arêtes entrantes. Dans un mode particulier, un coefficient de la matrice indique s'il existe une arête entre deux sommets: il est égal à 1 s'il existe une arête et 0 s'il n'en existe pas. Dans un autre mode, un coefficient de la matrice indique la valuation de l'arête correspondante. Dans la suite, nous utiliserons des 30 matrices d'adjacence ne comportant que des 0 et des 1. Lorsque x est un ensemble de chemins d'un épaississement g du graphe initial GO, on notera dans la suite, dumb(x) ", le raffinement trivial de x dans un raffinement du graphe auquel il appartient. Si x=(el, e2, ..., ek) avec el, e2, ... ek 35 des ensembles de sommets de g, et si g' est un raffinement de g, dumb(x) = (fl, f2, ..., fk) avec pour tout entier i dans [1, k], un sommet s' de g' appartient à fi si et seulement si il existe un sommet s de ei tel que s' est dans la classe de s. La description qui suit concerne un exemple de graphe. Il est entendu que le procédé conforme à l'invention est décrit ici à titre d'exemple, de façon à ce qu'un homme du métier puisse le reproduire. Considérons le graphe GO de la figure 1: Les arcs sortants et entrants sont: OutO = {(0,1,0,1,0), (0,0,1,0,0), (0,0,0,1,0), (0,1,0,0,1), (1,,0,0, 0,0)} 10 InO = {(0,0,0,0,1), (1,0,0,1,0), (0,1,0,0,0), (1,0,1,0,0), (0,0, 0,1,0)} Le premier épaississement de ce graphe GO est le graphe G 1 représenté sur la figure 2. 1 5 Les arcs entrants et sortants de ce graphe G1 sont: Outl = {(1,1,0), (1,1,1), (1,0,0)} In1 ={(1,1,1), (1,1,0), (0,1,0)} 20 Ce graphe s'épaissit à son tour en le graphe G2 représenté sur la figure 3. Les arcs entrants et sortants de ce graphe sont: Out2 = {(1,1), (1,0)} et In2 = {(1,1), (1, 0)}. Enfin ce graphe s'épaissit en le graphe G3 représenté sur la figure 4. Les arcs entrants et sortants de ce graphe sont: Out3 = {(1)} et In3 = {(1)}. Recherchons par exemple un chemin entre les sommets 2 et 5 dans le graphe GO. Recherche des chemins de longueur 1: Dans G3: le chemin trivial de longueur 1 est f->f. Dans G2: le sommet 2 est dans la classe d, le sommet 5 est dans la classe e. Il existe un arc entre d et e. Donc dans G2, on a le chemin d->e Dans gl: le sommet 2 est dans la classe a, le sommet 5 est dans la classe c. Il n'existe pas d'arc entre a et c. Donc il n'existe pas de chemin de longueur 1 entre 2 et 5. Recherche des chemins de longueur 2: Dans g3: les sommets 2 et 5 sont dans la classe de f. 20 Le chemin trivial de longueur 2 est f->f->f. Dans G2: le sommet 2 est dans la classe d, 5 est dans la classe e. 1 - Incréments d+1 = (1,1). On intersecte d + 1 avec dumb(f) = (1,1). Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1). Donc le deuxième arc donne (1,1)->(0,1). En résumé, les incréments donnent le chemin (1,0)-> (1,1)-> (0,1) 2Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0). 10 Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,0) donne (1,0). 15 Donc le premier arc donne (1,0) -> (1,0) On a donc un ensemble de chemins de longueur 2 dans G2 qui est: (1,0)-> (1,0)-> (0,1). 20 Dans gl 2 est dans la classe de a, 5 est dans la classe de c. 25 1 Incréments a + 1 = (1,1,0). Donc a+1 intersecté avec dumb(1,0) = (1,1,0) donne (1,1,0). Le premier arc donne donc (1,0,0) -> (1,1,0). 30 (1,1,0) + 1 = (1,1,1). Donc (1,1,0) + 1 intersecté avec dumb(1,0) = (1,1, 0) donne (1,1,0). Ce dernier vecteur intersecté avec (0,0,1) donne (0,0,0). 35 Le deuxième arc donne donc (1,1,0) -> (0,0,0) Donc l'incrément donne le chemin (1,0,0)-> (1,1,0)-> (0,0,0) On en conclut qu'il n' y a pas de chemin de longueur 2 dans gl, et a fortiori dans GO. Recherche des chemins de longueur 3: Dans G3, le chemin trivial est f->f-> f->f. Dans G2: le sommet 2 est dans la classe d, 5 est dans la classe e. 1 - Incréments d+1 = (1,1). On intersecte d + 1 avec dumb(f) = (1,1). Donc le premier arc donne (1,0)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f), ce qui donne (1,1) + 1 intersecté avec (1,1), soit (1,1). Donc le deuxième arc donne (1,1)->(1,1) Puis on fait (1,1) + 1 intersecté avec dumb(f) et arrivée, ce qui donne (1,1) + 1 intersecté avec (1,1) intersecté avec (0,1), soit (0,1). 30 Donc le troisième arc donne (1,1)->(0,1). En résumé, les incréments donnent le chemin (1,0) -> (1,1) ->(1,1)-> (0,1) 35 2- Décréments (0,1) - 1 {= (1,0)} intersecté avec (1,1) = (1,0). 1 1 Donc le dernier arc donne (1,0) -> (0,1) (1,0) - 1 = (1,1) intersecté avec (1,1) donne (1,1). Donc le deuxième arc donne (1,1) -> (1,0) (1,1)-1 intersecté avec (1,0) donne (1,0). 10 Donc le premier arc donne (1,0)->(1,1) On a donc un ensemble de chemins de longueur 3 dans g2 qui est: (1,0) -> (1,1)->(1,0) -> (0,1). Dans G1: le sommet 2 est dans la classe a, 5 est dans la classe c. 1 - Incréments a+1 = (1,1, 0). On intersecte a + 1 avec dumb(1,1) = (1,1, 1), ce qui donne (1,1,0). Donc le premier arc donne (1,0, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 intersecté avec dumb(1,0) = (1,1,0), ce qui donne (1,1,0) + 1 = (1,1,1) intersecté avec (1,1,0), soit (1,1,0). 30 Donc le deuxième arc donne (1,1, 0)->(1,1, 0) Puis on fait (1,1, 0) + 1 = (1,1,1) intersecté avec dumb(0,1) = (0,1,1) et arrivée, ce qui donne (1,1, 1) intersecté avec (0, 1,1) intersecté avec (0,0, 1), soit (0,0, 1). Donc le troisième arc donne (1,1, 0)->(0,0, 1). En résumé, les incréments donnent le chemin (1,0, 0) -> (1,1, 0) ->(1,1, O)-> (0,0, 1) 2 - Décréments (0, 0,1) - 1 {= (0,1,0)} intersecté avec (1,1,0) = (0, 1,0). Donc le dernier arc donne (0, 1,0) -> (0,0,1) (0,1,0) - 1 = (1,1,0) intersecté avec (1,1,0) donne (1,1, 0). Donc le deuxième arc donne (1,1, 0) -> (0, 1,0) 15 (1,1,0)-1 intersecté avec (1,0, 0) donne (1,0, 0). Donc le premier arc donne (1,0, 0)->(1,1, 0) On a donc un ensemble de chemins de longueur 3 dans gl qui est: 20 (1,0, 0) -> (1,1, 0)->(0, 1,0) -> (0, 0, 1). Dans GO: 1 - Incréments (0,1,0,0,0)+1 = (0,0,1, 0,0). On intersecte (0,1,0,0,0) + 1 avec dumb(1,1, 0) = (1,1, 1, 1, 0), ce qui 30 donne (0, 0,1,0, 0). Donc le premier arc donne (0, 1, 0, 0, 0)->(0, 0, 1, 0, 0). Puis on fait (0, 0, 1, 0, 0) + 1 intersecté avec dumb(1, 1,0) = (1,1,1, 1, 0), 35 ce qui donne (0, 0, 1,0, 0) + 1 = (0, 0, 0, 1,0) intersecté avec (1,1, 1, 1,0), soit (0, 0, 0, 1,0). Donc le deuxième arc donne (0, 0,1, 0, 0)->(0, 0, 0, 1, 0) Puis on fait (0, 0, 0, 1,0) + 1 = (1,0, 1, 0, 0) intersecté avec dumb(0, 0, 1) = (0,0, 0, 0, 1) et arrivée, ce qui donne: (1,0, 1, 0, 0) intersecté avec (0, 0, 0, 0, 1) intersecté avec (0,0, 0, 01), soit (0,0, 0, 0, 1). Donc le troisième arc donne (0, 0, 0, 1, 0)->(0,0, 0, 0, 1). En résumé, les incréments donnent le chemin (0, 1,0, 0, 0) -> (0, 0, 1, 0, 0)->(0, 0, 0, 1, 0)-> (0,0, 0, 0, 1) 15 2- Décréments (0, 0,0, 0, 1) - 1 {= (0, 0, 0, 1, 0)} intersecté avec (0, 0, 0,1,0) = (0, 0, 0, 1,0). 20 Donc le dernier arc donne (0, 0, 0, 1,0) -> (0,0, 0, 0, 1) (0,0,0,1,0) - 1 =(1,0,1,0,0) intersecté avec (0,0,1,0, 0) donne (0,0, 1,0, 0). Donc le deuxième arc donne (0, 0,1, 0, 0) -> (0, 0, 0, 1,0) (0, 0,1, 0, 0)-1 intersecté avec (0, 1,0, 0, 0) donne (0, 1, 0, 0, 0). Donc le premier arc donne (0, 1,0, 0, 0)->(0, 0,1, 0, 0) On a donc un ensemble de chemins de longueur 3 dans GO qui est: (0, 1,0, 0, 0) -> (0, 0,1,0, 0)->(0, 0, 0, 1,0) -> (0, 0, 0, 0,1). Finalement, on trouve le chemin 2->3->4->5 et c' est le chemin le plus 35 court. Le calcul du chemin le plus court étant réalisé en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur, il devient évident pour l'homme du métier, à la lecture des différentes étapes constituant l'exemple précédent, que le procédé selon l'invention possède un effet technique évident: l'optimisation des ressources mémoires et de l'utilisation du processeur. Cette optimisation se traduit, pour de longs calculs, par des gains de temps et des gains 5 financiers très significatifs. Elle peut également se traduire par des gains de place intéressants pour les calculs sur des systèmes embarqués. Certains domaines exigent de lourds calculs pour la recherche de plus courts chemins dans des graphes comme par exemple les télécommunications ou 1o le trafic routier. L'utilisation de machines informatiques implémentant le procédé selon l'invention permet d'optimiser les ressources nécessaires pour réaliser ces calculs. L'invention est décrite dans ce qui précède à titre d'exemple. Il est 15 entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet. REVENDICATIONS 1 - Procédé de calcul des plus courts chemins en terme de coût et de 5 nombre d'arêtes dans un graphe valué comportant des sommets et une matrice d'adjacence en utilisant des moyens de calcul comprenant des ressources mémoires et un processeur caractérisé en ce qu'il comporte les étapes consistant à * se ramener à des valuations entières non nulles; * éventuellement se ramener à des valuations toutes égales à 1 en intercalant des sommets entre tout couple de sommets reliés par une arête de valuation strictement supérieure à 1; * effectuer une série d'incrémentations, une incrémentation consistant à trouver l'ensemble des sommets auxquels on peut arriver en partant d'un 15 n-uplet de sommets donné; * effectuer une série de décrémentations, une décrémentation consistant à trouver l'ensemble des sommets à partir desquels on peut arriver à un nuplet de sommets donné; * les incrémentations et les décrémentations pouvant se succéder dans 20 n'importe quel ordre; * transformer les vecteurs d'incrément/décrément en chemins, ces chemins constituant l'ensemble E1 des chemins les plus courts en terme de nombre d'arêtes ou empruntant un nombre donné d'arêtes Na; * sélectionner le n-uplet de chemins C de moindre coût parmi l'ensemble 25 de chemins E1; * effectuer Nb= Na+ 1; * effectuer tant que (Nb ≤ v(C)) les étapes suivantes de manière itérative: examiner parmi les chemins de nombre d'arêtes Na + 1 ceux s'ils existent qui ont un coût strictement inférieure à v(C) et sélectionner parmi ceux-ci ceux C' de coût minimal (s'il n'existe pas de tel chemin, alors C'= C) * C=C'etNb = Nb + 1 les chemins les plus courts en terme de coût étant constitués par le nuplet C. 2 Procédé de calcul des plus courts chemins en terme de coût et de 5 nombre d'arêtes dans un graphe valué GO selon la revendication 1 caractérisé en ce qu'il comporte en outre l'étape consistant à effectuer des raffinements successifs du chemin dit " 3 - Procédé de calcul des plus courts chemins en terme de coût et de nombre d'arêtes dans un graphe valué GO selon la revendication 1 ou 2 caractérisé en ce que la série d'incrémentations s'effectue dans un épaississement du graphe 15 initial jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb; et en ce qu'il comporte en outre les étapes suivantes: * on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée dans le même épaississement du graphe; * on raffine alors le chemin obtenu jusqu'à obtenir les plus courts chemins empruntant Nb arêtes dans le graphe initial, s'il en existe; * s'il n'en n'existe pas, on pose Nb = Nb +1, et on recherche les plus courts chemins empruntant Nb arcs dans un épaississement du graphe initial, qu'on tente de raffiner dans le graphe initial comme à l'étape 25 précédente. on recommence la présente étape tant qu'un plus court chemin n'a pas été trouvé. 4 - Procédé de calcul des plus courts chemins en terme de coût et de nombre d'arêtes dans un graphe valué GO selon la revendication 1, 2 ou 3 30 caractérisé en ce qu'il comporte en outre une étape de pré-calcul consistant à réaliser des épaississements successifs du graphe GO jusqu'à l'obtention d'un graphe G1 ne comportant plus qu'un seul sommet et un seul arc, un épaississement du graphe G consistant à * munir le graphe G d'une relation d'équivalence; * considérer que les classes d'équivalence sont les sommets du graphe épaissi G';' * étant donné deux sommets S1 et S2 du graphe épaissi G', il existe un arête entre S1 et S2 si et seulement si il existe sl appartenant à S1 et s2 appartenant à S2 tels que sl et s2 sont reliés par une arête dans G; * la valuation de l'arête S1-S2 de G'étant le minimum des valuations des arêtes sl-s2 de G, avec sl appartenant à S1 et s2 appartenant à S2. - Procédé de calcul des plus courts chemins en terme de coût et de nombre d'arêtes dans un graphe valué selon la revendication 1, 2 ou 3 caractérisé en ce que * la série d'incrémentations s'effectue jusqu'à ce que le sommet d'arrivée soit contenu dans l'ensemble obtenu à partir du sommet de départ, ce qui fournit un chemin de longueur Nb * on intersecte les ensembles obtenus avec les décréments du sommet d'arrivée. 6 - Procédé de calcul des plus courts chemins en terme de nombre d'arêtes dans un graphe valué selon la revendication 1, 2, caractérisé en ce qu'il est appliqué au routage de paquets dans un télécommunications. 7 - Procédé de calcul des plus courts chemins en terme de nombre d'arêtes dans un graphe valué selon la revendication 1, 2, caractérisé en ce qu'il est appliqué au routage d'appels dans un télécommunications. coût et de 3, 4 ou 5 réseau de coût et de 3, 4 ou 5 réseau de 8 - Procédé de calcul des plus courts chemins en terme de nombre d'arêtes dans un graphe valué selon la revendication 1, 2, caractérisé en ce qu'il est appliqué à un système de navigation. 9 - Procédé de calcul des plus courts chemins en terme de nombre d'arêtes dans un graphe valué selon la revendication 1, 2, caractérisé en ce qu'il est appliqué à un système de réservation. coût et de 3, 4 ou 5 coût et de 3, 4 ou 5 - Procédé de calcul des plus courts chemins en terme de coût et de 35 nombre d'arêtes dans un graphe valué selon la revendication 1, 2, 3, 4 ou 5 caractérisé en ce qu'il est appliqué à un système automatisé d'aide à la traduction. 2855287 18 11 - Système pour la mise en oeuvre du procédé selon l'une quelconque des revendications précédentes comprenant au moins un processeur et des ressources mémoire.