Voir le texte source

== Généralités==
''<u>Remarques et définitions :</u>''
* ''Nous nous intéresserons aux chemins de longueur non nulle.''
* ''Nous allons travailler sur des graphes orientés valués.''
* ''Le coût (poids ou valeur) d'un chemin est égal à la somme des coûts des arcs qui le composent. On l'appelle aussi '''la distance''' du chemin.''
* ''Le plus court chemin d'un sommet '''x''' vers un sommet '''y''' est le chemin de coût minimum allant de '''x''' vers '''y'''. Un tel chemin n'existe pas forcément.''
* ''La plus petite distance d'un sommet '''x''' vers un sommet '''y''' est le coût du plus court chemin s'il existe.''

<br/>


''<u>Conditions d'existence:</u>''

Considérons un chemin '''''M''''' allant d'un sommet '''''x''''' à un sommet '''''y'''''. Supposons que ce chemin possède un circuit '''''T'''''. Appelons '''''M'''''' le chemin obtenu en retirant '''''T''''' de '''''M''''', on a alors la relation de coût suivante:
 Coût('''''M''''') = Coût('''''M'''''') + Coût('''''T''''')
Si le Coût('''''T''''') est négatif (<0), il n'existe dans ce cas pas de plus court chemin allant de '''''x''''' à '''''y'''''. En effet, il suffit de repasser une fois de plus par le circuit '''''T''''' pour obtenir un meilleur résultat (chemin de coût inférieur).

''Un tel circuit est appelé '''circuit absorbant'''.''

Si le Coût('''''T''''') est nul (=0), '''''M'''''' est de coût égal à celui de '''''M'''''. Dans ce cas c'est aussi un plus court chemin, mais sa longueur (nombre de sommets empruntés) est supérieure à celle de '''''M'''''.

Si le Coût('''''T''''') est positif (>0), '''''M'''''' est de coût inférieur à celui de '''''M'''''. Dans ce cas c'est un meilleur candidat que '''''M''''' au titre de plus court chemin.

S'il existe des circuits, ils sont de coût positif ou nul. Or un plus court chemin ne peut pas contenir de circuit de coût strictement positif et s'il existe des circuits de coût nul, il y a plusieurs solutions au problème de la recherche de plus court chemin.

Comme le nombre de chemin élémentaires (ne passant pas plusieurs fois par un même sommet), allant d'un sommet '''''x''''' à un sommet '''''y''''', est fini, il existe au moins un plus court chemin élémentaire allant de '''''x''''' vers '''''y''''' (''note: Il peut en exister plusieurs'').
<br/>

'''''En conclusion: Il existe une solution au problème de la recherche d'un plus court chemin allant de '''''x''''' à '''''y''''' s'il existe un chemin de '''''x''''' à '''''y''''' et s'il n'y a pas de circuit absorbant.'''''

<br/>

''<u>Variantes du problème:</u>''

Les algorithmes que nous allons présenter fournissent, dans le cas où il n'y a pas de circuit absorbant, un plus court chemin élémentaire.

Les trois possibilités de rechercher un plus court chemin sont: 
# entre deux sommets '''''x''''' et '''''y''''',
# d'un sommet '''''x''''' (une source) vers tous les autres sommets du graphe,
# entre tous les couples de sommets '''''x''''' et '''''y'''''.

<br/>

''Remarques:''
* ''Le 1) étant obtenu en meilleur solution du 2), nous ne nous intéresserons qu'au 2) et 3).''
* ''Il n'existe pas d'algorithme général que ce soit pour le 2) ou le 3). Il faut tenir compte des propriétés des graphes manipulés et du problème posé et dès lors choisir l'algorithme le plus adapté.''
<br/>

==Dijkstra==
L'algorithme de Dijkstra n'est utilisable que dans les cas, très fréquents, où les coûts des arcs sont positifs ou nuls. Il détermine le plus court chemin entre un sommet de départ '''''x''''' et tous les autres sommets du graphe accessibles depuis '''''x'''''.
On obtient alors un arbre de racine '''''x''''' formé par les plus courts chemins de '''''x''''' vers les sommets qu'il peut atteindre. Il est à noter que n'ayant pas de coûts négatifs, il accepte les graphes présentant des circuits.

===Principe===
Soit '''''G=< S,A,C >''''' un graphe orienté valué de '''''n''''' sommets.
Soit '''''x''''' un sommet de '''''S''''', on se propose de construire un ensemble '''''CC''''' (court chemin) de sommets '''''y''''' pour lesquels on connait un plus court chemin depuis '''''x'''''.

* Au départ, '''''CC''''' ne contient que la source ('''''x'''''). 
* A chaque étape, on ajoute à '''''CC''''' un sommet '''''y''''' pour lequel la plus petite distance ('''ppdistance(''x,y,G'')''') et le père ('''pere(''x,y,G'')''') sont connus.
* On s'arrête lorsque '''''CC''''' contient tous les sommets accessibles depuis '''''x'''''.

Soit '''''M''''' le complémentaire de '''''CC''''' dans '''''S''''' ('''''M=S-CC''''') et quel que soit '''''y''''' un sommet de '''''M''''', on appelle '''chemin de ''x'' à ''y'' dans ''CC''''' tout chemin allant de  '''''x''''' à '''''y''''' ne comprenant que des sommets de '''''CC''''' sauf '''''y''''' (voir figure 1.).

{| align="center" border="1" cellpadding="10"
|+ '''Figure 1. Chemins de ''x'' à ''y'' dans ''CC'''''.
|  align="center" | [[Image:pcchemin_dijkstra_1.png| 250px | ''Chemin de x à y dans CC.'']]
|}
<br/>

On note alors '''distance<sub>''x,CC''</sub>(''y'')''', le coût du plus court chemin allant de '''''x''''' à '''''y''''' dans '''''CC''''' et '''pred<sub>''x,CC''</sub>(''y'')''' le prédecesseur de '''''y''''' dans ce plus court chemin.

A chaque étape, on choisit un sommet '''''m''''' de '''''M''''' tel que:
 '''distance<sub>''x,CC''</sub>(''m'') = Min{'''distance<sub>''x,CC''</sub>(''y'')'''} <math>\forall y \in M</math>'''

===Algorithme===

L'algorithme va parcourir le graphe '''''g''''' à partir du sommet source '''''x''''' et retournera deux tableaux: '''''ppd''''' et '''''pr''''' pour mémoriser les plus courts chemins et leur distance respective. '''''ppd[y]''''' mémorisera '''distance<sub>''x,CC''</sub>(''y'')''' et '''''pr[y]''''' mémorisera '''pred<sub>''x,CC''</sub>(''y'')'''.

Pour éviter des tests inutiles, nous allons étendre les capacités de la fonction de coût pour qu'elle soit définie quelque soit le couple de sommet ('''''x,y'''''), soit :
 '''coût(''x,x,g'') = 0''' pour un graphe sans boucle
 <br/>
 '''coût(''x,y,g'') = <math>\infty</math> ''' si '''''x'' arc ''y'' = faux'''

Nous utiliserons aussi une opération '''choisirmin(''M, ppd'')''' qui renverra le sommet <math>m\in M</math> tel que ppd[m] est minimum, ainsi que les opérations sur les ensembles. 

Pour l'algorithme de Dijkstra, les types de données employés sont les suivants :

 <span style="color:#0000FF;">'''Constantes'''</span><br/>
    Nbs = ...                           <span style="color:#00FF00;">/* Nombre de sommets du graphe */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_vectNbsReel = Nbs reel            <span style="color:#00FF00;">/* Vecteur de Nbs réels */</span>
    t_vectNbsEnt = Nbs entier           <span style="color:#00FF00;">/* Vecteur de Nbs réels */</span>

Ce qui donne:

 '''Algorithme procédure''' Dijkstra
 '''Paramètres locaux'''
    entier x                            <span style="color:#00FF00;">/* x est le sommet source */</span>
    graphe g
 '''Paramètres globaux'''
    t_vectNbsRéel ppd                   <span style="color:#00FF00;">/* ppd[y] est la distance du plus court chemin de x vers y*/</span>
    t_vectNbsEnt  pr                    <span style="color:#00FF00;">/* pr[y] est le prédécesseur de y sur ce chemin */</span>
 '''Variables'''
    entier i, y, m                      <span style="color:#00FF00;">/* y et m sont des sommets */</span>
    réel v
    ensemble M
 '''Début'''
    <span style="color:#00FF00;">/* Initialisation et marquage */</span>
    M <math>\leftarrow</math> ensemblevide
    '''pour''' i <math>\leftarrow</math> 1 '''jusqu'à''' n '''faire'''
       ppd[i] <math>\leftarrow</math> coût(x,i,g)
       pr[i] <math>\leftarrow</math> x
       M <math>\leftarrow</math> ajouter(i,M)
    '''fin pour'''
    M <math>\leftarrow</math> supprimer(x,M)                      <span style="color:#00FF00;">/* CC={x} */</span>
    <span style="color:#00FF00;">/* Ajouts successifs de sommets à CC */</span>
    '''tant que''' M <> ensemblevide '''faire'''
       m <math>\leftarrow</math> choisirmin(M,ppd)
       '''si''' ppd[m] = <math>\infty</math> '''alors'''                   <span style="color:#00FF00;">/* plus de sommets accessibles depuis x */</span>
          '''retourne'''
       '''fin si''' 
       M <math>\leftarrow</math> supprimer(m,M)                   <span style="color:#00FF00;">/* ajout de m à CC */</span>
       <span style="color:#00FF00;">/* réajustement des valeurs de distance */</span>
       '''pour''' i <math>\leftarrow</math> 1 '''jusqu'à''' d<sup>o+</sup>(m,g) '''faire'''
          y <math>\leftarrow</math> ième-succ(i,m,g)
          '''si''' y <math>\in</math> M '''alors'''                    <span style="color:#00FF00;">/* Plus court chemin de x à y pas encore déterminé */</span>
             v <math>\leftarrow</math> ppd[m] + coût(m,y,g)
             '''si''' v < ppd[y] '''alors'''   
                ppd[y] <math>\leftarrow</math> v
                pr[y] <math>\leftarrow</math> m
             '''fin si'''
          '''fin si'''
       '''fin pour'''
    '''fin tant que'''
 '''Fin Algorithme procédure''' Dijkstra
<br/>

Appliquons l'algorithme de Dijsktra au graphe orienté valué de la figure 2 en prenant le sommet '''''1''''' comme sommet source (nous cherchons à déterminer les plus courts chemins depuis '''''1''''' vers tous les autres.
 
''Note: les sommets sont traités en ordre croissants, que ce soit dans l'ensemble '''M''' ou en tant que successeurs.''
<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 2. Graphe orienté valué ''G''.'''
|  align="center" | [[Image:diskstragraphereference.png|350px | ''graphe orienté valué'']]
|}
<br/>

Après exécution de l'algorithme '''dijkstra''', nous obtenons les vecteurs '''''ppd''''' et '''''pr''''' suivants (tableau 1) :

{| align="center" border="1" cellpadding="10"
|+ '''Tableau 1. Vecteurs ''ppd'' et ''pr'' résultants de l'application de l'algorithme de Dijkstra appliqué au graphe de la figure 2.'''
| align="right" | Sommets (indice)
| align="left" | 1
| align="left" | 2
| align="left" | 3
| align="left" | 4
| align="left" | 5
| align="left" | 6
| align="left" | 7
| align="left" | 8
|-
| align="right" | PPD
| align="center" | 0
| align="center" | 1
| align="center" | 0
| align="center" | 2
| align="center" | 1
| align="center" | 3
| align="center" | 2
| align="center" | 2
|-
| align="right" | PR
| align="center" | 1
| align="center" | 3
| align="center" | 1
| align="center" | 2
| align="center" | 3
| align="center" | 5
| align="center" | 1
| align="center" | 7
|}
<br/>

Ce qui correspond à l'arbre de racine '''''1''''' suivant (voir figure 3):

{| align="center" border="1" cellpadding="10"
|+ '''Figure 3. Arbre des plus courts chemins depuis ''1''.'''
|  align="center" | [[Image:diskstraarbreobtenu.png |170px | ''Arbre des plus courts chemins.'']]
|}
<br/>

Par exemple, pour connaître le plus court chemin du sommet '''''1''''' au sommet '''''4''''', il suffit de remonter la parenté depuis le sommet '''''4''''' (destination) jusqu'au sommet '''''1''''' (la source) en utilisant le vecteur '''pr'''. Son coût (plus petite distance) étant obtenu par '''ppd[''4'']''', ce qui donne :

 plus court chemin de 1 à 4 : 1<math>\rightarrow</math>3<math>\rightarrow</math>2<math>\rightarrow</math>4 de coût : 2
<br/>

==Bellman==
L'algorithme de Bellman est utilisable dans les cas où les coûts des arcs sont quelconques, mais où le graphe ne présente pas de circuit. Il détermine le plus court chemin entre un sommet de départ '''''x''''' (racine du graphe) et tous les autres sommets du graphe accessibles depuis '''''x'''''. On obtient alors un arbre de racine '''''x''''' formé par les plus courts chemins de '''''x''''' vers les sommets qu'il peut atteindre.

===Principe===
Soit '''''G=< S,A,C >''''' un graphe orienté valué de '''''n''''' sommets.
Soit '''''x''''' un sommet de '''''S''''', on se propose de construire un ensemble '''''CC''''' (court chemin) de sommets '''''y''''' pour lesquels on connait un plus court chemin depuis '''''x'''''. Soit '''''M''''', complémentaire de '''''CC''''' dans '''''S''''' ('''''M=S-CC'''''), l'ensemble des sommets '''''y''''' pour lesquels '''ppdistance(''x,y,G'')''' n'est pas encore déterminée. 

On ne calcule '''ppdistance(''x,y,G'')''' que lorsque tous les prédécesseurs de '''''y''''' sont dans '''''CC'''''. 

<math>\Rightarrow \forall y \in S,</math> il faut connaître son demi-degré intérieur (nombre de prédécesseurs) et pouvoir accèder à son i<sup>ème</sup> prédécesseur.

<br/>

<u>L'idée est la suivante:</u>

Un plus court chemin allant de  '''''x''''' à '''''y''''' passe obligatoirement par un des prédécesseurs '''''m''''' de '''''y''''' (voir figure 4), celui pour lequel '''ppdistance(''x,m,G'') + coût(''m,y,G'')''' est minimum.

{| align="center" border="1" cellpadding="10"
|+ '''Figure 4. Chemins de ''x'' à ''y'' dans ''CC'''''.
|  align="center" | [[Image:pcchemin_dijkstra_1.png |250px | ''Chemin de x à y dans CC.'']]
|}
<br/>

===Algorithme===

L'algorithme retournera deux tableaux: '''''ppd''''' et '''''pr''''' pour mémoriser les plus courts chemins et leur distance respective. '''''ppd[y]''''' mémorisera '''distance<sub>''x,CC''</sub>(''y'')''' et '''''pr[y]''''' mémorisera '''pred<sub>''x,CC''</sub>(''y'')'''.

Pour éviter des tests inutiles, nous allons étendre les capacités de la fonction de coût pour qu'elle soit définie quelque soit le couple de sommet ('''''x,y'''''), soit :
 '''coût(''x,x,g'') = 0''' pour un graphe sans boucle
 <br/>
 '''coût(''x,y,g'') = <math>\infty</math> ''' si '''''x'' arc ''y'' = faux'''

* Au départ, '''''CC''''' ne contient que la source ('''''x'''''). 
* A chaque étape L'algorithme choisit donc dans '''''M''''' un sommet '''''y''''' tel que tous ses prédécesseurs soient dans '''''CC'''''. On regarde par lequel de ses prédécesseurs, le chemin depuis '''''x''''' est le plus court. Ce sommet est alors ajouté à '''''CC''''' et les vecteurs '''ppd''' et '''pr''' sont mis à jour.
* On s'arrête lorsque '''''M''''' est vide.

Nous utiliserons une opération '''choisirsuivant(''M, g'')''' qui renverra un sommet de '''''M''''' n'ayant plus aucun prédécesseurs dans '''''M'''''.

Pour l'algorithme de Bellman, les types de données employés sont les suivants :

 <span style="color:#0000FF;">'''Constantes'''</span><br/>
    Nbs = ...                           <span style="color:#00FF00;">/* Nombre de sommets du graphe */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_vectNbsReel = Nbs reel            <span style="color:#00FF00;">/* Vecteur de Nbs réels */</span>
    t_vectNbsEnt = Nbs entier           <span style="color:#00FF00;">/* Vecteur de Nbs réels */</span>

Ce qui donne:

 '''Algorithme procédure''' Bellman
 '''Paramètres locaux'''
    entier x                            <span style="color:#00FF00;">/* x est le sommet source */</span>
    graphe g
 '''Paramètres globaux'''
    t_vectNbsRéel ppd                   <span style="color:#00FF00;">/* ppd[y] est la distance du plus court chemin de x vers y*/</span>
    t_vectNbsEnt  pr                    <span style="color:#00FF00;">/* pr[y] est le prédécesseur de y sur ce chemin */</span>
 '''Variables'''
    entier i, y, z, m                   <span style="color:#00FF00;">/* y, z et m sont des sommets */</span>
    réel min, aux                       <span style="color:#00FF00;">/* min et aux sont des distances */</span>
    ensemble M
 '''Début'''
    <span style="color:#00FF00;">/* Initialisation et marquage */</span>
    M <math>\leftarrow</math> ensemblevide
    '''pour''' i <math>\leftarrow</math> 1 '''jusqu'à''' n '''faire'''
       M <math>\leftarrow</math> ajouter(i,M)
    '''fin pour'''
    M <math>\leftarrow</math> supprimer(x,M)                      <span style="color:#00FF00;">/* CC={x} */</span>
    ppd[x] <math>\leftarrow</math> 0
    pr[x] <math>\leftarrow</math> x
    '''tant que''' M <> ensemblevide '''faire'''
    <span style="color:#00FF00;">/* Ajouts successifs de sommets à CC */</span>
       m <math>\leftarrow</math> choisirsuivant(M,g)
       M <math>\leftarrow</math> supprimer(m,M)                   <span style="color:#00FF00;">/* ajout de m à CC */</span>
       y <math>\leftarrow</math> ième-pred(1,m,g)                 <span style="color:#00FF00;">/* Premier prédécesseur et sa distance associée */</span>
       min <math>\leftarrow</math> ppd[y] + coût(y,m,g)
       <span style="color:#00FF00;">/* comparaison avec les autres prédecesseurs */</span>
       '''pour''' i <math>\leftarrow</math> 2 '''jusqu'à''' d<sup>o-</sup>(m,g) '''faire'''
          z <math>\leftarrow</math> ième-pred(i,m,g)              <span style="color:#00FF00;">/* ième prédécesseur et sa distance associée */</span>
          aux <math>\leftarrow</math> ppd[z] + coût(z,m,g)
          '''si''' aux < min '''alors'''                <span style="color:#00FF00;">/* Plus court chemin de x à y pas encore déterminé */</span>
             min <math>\leftarrow</math> aux
             y <math>\leftarrow</math> z
          '''fin si'''
       '''fin pour'''
       ppd[x] <math>\leftarrow</math> min
       pr[x] <math>\leftarrow</math> y
    '''fin tant que'''
 '''Fin Algorithme procédure''' Bellman
<br/>

Appliquons l'algorithme de Bellman au graphe orienté valué de la figure 5 en prenant le sommet '''''1''''' comme sommet source (nous cherchons à déterminer les plus courts chemins depuis '''''1''''' vers tous les autres.
 
''Note: les sommets sont traités en ordre croissants, que ce soit dans l'ensemble '''M''' ou en tant que successeurs.''
<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 5. Graphe orienté valué ''G'' coûts quelconques (sans circuit).'''
|  align="center" | [[Image:bellmangraphereference.png|350px | ''graphe orienté valué à coûts quelconques (sans circuit)'']]
|}
<br/>

Après exécution de l'algorithme '''Bellman''', nous obtenons les vecteurs '''''ppd''''' et '''''pr''''' suivants (tableau 2) :

{| align="center" border="1" cellpadding="10"
|+ '''Tableau 2. Vecteurs ''ppd'' et ''pr'' résultants de l'application de l'algorithme de Bellamn appliqué au graphe de la figure 5.'''
| align="right" | Sommets (indice)
| align="left" | 1
| align="left" | 2
| align="left" | 3
| align="left" | 4
| align="left" | 5
| align="left" | 6
| align="left" | 7
| align="left" | 8
|-
| align="right" | PPD
| align="center" | 0
| align="center" | -1
| align="center" | 0
| align="center" | -3
| align="center" | 1
| align="center" | -5
| align="center" | -2
| align="center" | -2
|-
| align="right" | PR
| align="center" | 1
| align="center" | 5
| align="center" | 1
| align="center" | 5
| align="center" | 3
| align="center" | 8
| align="center" | 1
| align="center" | 7
|}
<br/>

Ce qui correspond à l'arbre de racine '''''1''''' suivant (voir figure 6):

{| align="center" border="1" cellpadding="10"
|+ '''Figure 6. Arbre des plus courts chemins depuis ''1''.'''
|  align="center" | [[Image:bellmanarbreobtenu.png |170px | ''Arbre des plus courts chemins.'']]
|}
<br/>

Par exemple, pour connaître le plus court chemin du sommet '''''1''''' au sommet '''''4''''', il suffit de remonter la parenté depuis le sommet '''''4''''' (destination) jusqu'au sommet '''''1''''' (la source) en utilisant le vecteur '''pr'''. Son coût (plus petite distance) étant obtenu par '''ppd[''4'']''', ce qui donne :

 plus court chemin de 1 à 4 : 1<math>\rightarrow</math>3<math>\rightarrow</math>5<math>\rightarrow</math>4 de coût : -3
<br/>

==Floyd==
L'algorithme de Floyd est utilisable dans les cas où les coûts des arcs sont quelconques, avec ou sans cirscuits, mais sans circuit absorbant. Il détermine le plus court chemin entre tous les couples de sommet ('''''x,y''''') d'un graphe '''''G'''''.

''Nous pourrions utiliser les algorithmes de [[Epita:Algo:Cours:Info-Spe:les plus courts chemins#Bellman|'''Bellman''']] ou de [[Epita:Algo:Cours:Info-Spe:les plus courts chemins#Dijkstra|'''Dijkstra''']] en faisant varier la racine, mais pas pour des graphes à coûts quelconques et présentant des circuits non absorbants.''

L'algorithme de Floyd fait partie des algorithmes simples qui déterminent tous les plus courts chemins en utilisant une représentation matricielle.

===Principe===
Le principe de cet algorithme est le même que celui de [[Epita:Algo:Cours:Info-Spe:les connexités#Algorithme de WARSHALL|'''l'algorithme de Warshall''']] utilisé pour déterminer la fermeture transitive d'un graphe (''connexité du graphe'').

Soit '''''G=< S,A,C >''''' un graphe orienté valué de '''''n''''' sommets.

* Au départ, on considère uniquement les chemins de '''''x''''' à '''''y''''' qui ne passent par aucun autre sommet du graphe. On a alors '''ppdistance(''x,y,G'') = coût(''x,y,G'')''' et '''pere(''x,y,G'') = ''x'''''. 
* A chaque étape '''''i''''', on calcule '''distance<sub>i</sub>(''x,y'')''' le coût du plus court chemin allant de '''''x''''' à '''''y''''' passant par des sommets inférieurs ou égaux à '''''i'''''. Si celui-ci est inférieur à la plus petite distance connue actuellement, il devient cette plus petite distance et '''pere(''i,y,G'')''' remplace '''pere(''x,y,G'').

===Algorithme===

L'algorithme utilisera deux matrices: '''''ppd''''' et '''''pr''''' pour mémoriser les plus courts chemins et leur distance respective. '''''ppd[x,y]''''' mémorisera '''ppdistance<sub>''i''</sub>(''x,y'')''' et '''''pr[x,y]''''' mémorisera '''pere<sub>''i''</sub>(''x,y'')'''.

Pour éviter des tests inutiles, nous allons étendre les capacités de la fonction de coût pour qu'elle soit définie quelque soit le couple de sommet ('''''x,y'''''), soit :
 '''coût(''x,x,g'') = 0''' pour un graphe sans boucle
 <br/>
 '''coût(''x,y,g'') = <math>\infty</math> ''' si '''''x'' arc ''y'' = faux'''

* Au départ, '''''ppd''''' et '''''pr''''' sont initialisés respectivement par '''coût(''x,y,G'')''' et '''''x'''''. 
* A chaque étape '''''i''''', ces deux matrices sont mises à jour par les éventuels plus courts chemins rencontrés passant par des sommets inférieurs ou égaux à '''''i'''''.

Pour l'algorithme qui suit, les type de données employés sont les suivants :

 <span style="color:#0000FF;">'''Constantes'''</span><br/>
    Nbs = ...                            <span style="color:#00FF00;">/* Nombre de sommets du graphe */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_matNbsNbsréel = Nbs x Nbs réel     <span style="color:#00FF00;">/* Matrice réelle carrée de Nbs sommets */</span>
    t_matNbsNbsent = Nbs x Nbs entier    <span style="color:#00FF00;">/* Matrice enière carrée de Nbs sommets */</span>

Ce qui donne:

 '''Algorithme procédure''' Floyd
 '''Paramètres locaux'''
    graphe g
 '''Paramètres globaux'''
    t_matNbsNbsréel ppd                  <span style="color:#00FF00;">/* Matrice d'adjacence du graphe g */</span>
    t_matNbsNbsent pr                    <span style="color:#00FF00;">/* Matrice d'adjacence du graphe g* */</span>
 '''Variables'''
    entier i, x, y                       <span style="color:#00FF00;">/* i, x et y sont des sommets */</span>
 '''Début'''
    <span style="color:#00FF00;">/* Initialisation de ppd et pr */</span>    
    '''pour''' x <math>\leftarrow</math> 1 '''jusqu'à''' Nbs '''faire''' 
       '''pour''' y <math>\leftarrow</math> 1 '''jusqu'à''' Nbs '''faire'''
          ppd[x,y] <math>\leftarrow</math> coût(x,y,g)
          pr[x,y] <math>\leftarrow</math> x
       '''fin pour'''
    '''fin pour'''<br/>
    <span style="color:#00FF00;">/* Calcul des plus courts chemins */</span>    
    '''pour''' i <math>\leftarrow</math> 1 '''jusqu'à''' Nbs '''faire'''
       '''pour''' x <math>\leftarrow</math> 1 '''jusqu'à''' Nbs '''faire'''
          '''pour''' y <math>\leftarrow</math> 1 '''jusqu'à''' Nbs '''faire'''
             '''si''' ppd[x,i] + ppd[i,y] < ppd[x,y] '''alors'''
                ppd[x,y] <math>\leftarrow</math> ppd[x,i] + ppd[i,y]
                pr[x,y] <math>\leftarrow</math> pr[i,y]
             '''fin si''' 
          '''fin pour'''
       '''fin pour'''
    '''fin pour'''
 '''Fin Algorithme procédure''' Floyd

Appliquons l'algorithme de Floyd au graphe orienté valué de la figure 7.
<br/>

{| align="center" border="1" cellpadding="10"
|+ '''Figure 7. Graphe orienté valué ''G'' coûts quelconques et circuits.'''
|  align="center" | [[Image:floydgraphereference.png|350px | ''graphe orienté valué à coûts quelconques et circuits'']]
|}
<br/>

Après exécution de l'algorithme '''Floyd''', nous obtenons les matrices '''''ppd''''' et '''''pr''''' suivantes (tableau 3) :

{| align="center" border="1" cellpadding="10"
|+ '''tableau 3. Evolutions des matrices ''ppd'' et ''pr'' lors de l'application de l'algorithme de Floyd appliqué au graphe de la figure 7.'''
|  align="center" | [[Image:floyd_matrices_6sommets2.png|500px | ''Evolutions des matrices ppd et pr'']]
|}
<br/>

Par exemple, pour connaître le plus court chemin allant du sommet '''''6''''' au sommet '''''3''''', il suffit de remonter la parenté depuis le sommet '''''3''''' (destination) jusqu'au sommet '''''6''''' (la source) en utilisant le vecteur '''pr'''. Son coût (plus petite distance) étant obtenu par '''ppd[''6,3'']''', ce qui donne :
<br/>
 pr[6,3] (4)
 pr[6,4] (2)
 pr[6,2] (1)
 pr[6,1] (6)
 <br/>
 Le chemin est donc : 6 -> 1 -> 2 -> 4 -> 3 de coût ppd[6,3] soit 4

----
<small>''(Christophe "krisboul" Boullay)''</small>