Problèmes de chemins
131
Si
est l'élément de
:
On voit que
représente la valeur du chemin de valeur minimale parmi les chemins
de longueur inférieure ou égale à 2 reliant
. Il suffit alors de composer :
4
2
2
= M
M
M
De la même façon pour obtenir la valeur des chemins minimaux et de longueur
inférieure ou égale à 4 reliant deux sommets quelconques. On constitue en composant :
k
k
k
M
M
M
2
=
En principe, on s'arrête lorsque k atteint ou dépasse
étant étant le nombre de
sommets. En fait, on peut voir facilement qu'il suffit de s'arrêter lorsque
.
On remarquera que cette méthode impose en principe de réserver en mémoire
d'ordinateur la place suffisante pour deux matrices
: pour un donné
et
.
Pour des graphes importants, cette nécessité est susceptible de créer quelque limitation
au niveau de l'utilisation de cette méthode. On remarquera néanmoins que lorsque l'on a
et que l'on calcule
, on peut remplacer au fur et à mesure les
de
par les
de
, ce qui permet de ne réserver de la place en mémoire que pour une matrice
).
( n
n
Il existe encore de nombreux autres algorithmes de détermination de plus courts chemins
sur un graphe valué par des longueurs positives, dont certains ne constituent que des
variantes des algorithmes que nous venons d'exposer.
Ils ont chacun leurs avantages et leurs inconvénients propres, variables d'ailleurs suivant
la configuration du graphe utilisé. Avant de choisir l'utilisation de tel ou tel algorithme, il
convient de se poser un certain nombre de questions, par exemple :
- veut-on la description complète des chemins de valeur minimale ou seulement
la valeur de ces chemins (choix entre algorithmes de type Ford ou Moore
Dijsktra et algorithmes matriciels) ?
- veut-on connaître le chemin le plus court reliant deux sommets particuliers ou
les chemins reliant plusieurs couples de sommets (choix entre Ford et
Bellmann-Kalaba ou Moore Dijkstra) ?
- dans quelle mesure la taille du graphe peut-elle limiter l'utilisation de
l'ordinateur par les problèmes d'encombrement-mémoire (difficulté de la
méthode matricielle, en particulier) ?
- aura-t-on à refaire plusieurs fois les calculs sur le même graphe (dans le cas par
exemple où les longueurs de certains arcs peuvent être sujettes à modification :
certains algorithmes permettent alors de ne pas recommencer totalement la
procédure) ?
131
Si
est l'élément de
:
On voit que
représente la valeur du chemin de valeur minimale parmi les chemins
de longueur inférieure ou égale à 2 reliant
. Il suffit alors de composer :
4
2
2
= M
M
M
De la même façon pour obtenir la valeur des chemins minimaux et de longueur
inférieure ou égale à 4 reliant deux sommets quelconques. On constitue en composant :
k
k
k
M
M
M
2
=
En principe, on s'arrête lorsque k atteint ou dépasse
étant étant le nombre de
sommets. En fait, on peut voir facilement qu'il suffit de s'arrêter lorsque
.
On remarquera que cette méthode impose en principe de réserver en mémoire
d'ordinateur la place suffisante pour deux matrices
: pour un donné
et
.
Pour des graphes importants, cette nécessité est susceptible de créer quelque limitation
au niveau de l'utilisation de cette méthode. On remarquera néanmoins que lorsque l'on a
et que l'on calcule
, on peut remplacer au fur et à mesure les
de
par les
de
, ce qui permet de ne réserver de la place en mémoire que pour une matrice
).
( n
n
Il existe encore de nombreux autres algorithmes de détermination de plus courts chemins
sur un graphe valué par des longueurs positives, dont certains ne constituent que des
variantes des algorithmes que nous venons d'exposer.
Ils ont chacun leurs avantages et leurs inconvénients propres, variables d'ailleurs suivant
la configuration du graphe utilisé. Avant de choisir l'utilisation de tel ou tel algorithme, il
convient de se poser un certain nombre de questions, par exemple :
- veut-on la description complète des chemins de valeur minimale ou seulement
la valeur de ces chemins (choix entre algorithmes de type Ford ou Moore
Dijsktra et algorithmes matriciels) ?
- veut-on connaître le chemin le plus court reliant deux sommets particuliers ou
les chemins reliant plusieurs couples de sommets (choix entre Ford et
Bellmann-Kalaba ou Moore Dijkstra) ?
- dans quelle mesure la taille du graphe peut-elle limiter l'utilisation de
l'ordinateur par les problèmes d'encombrement-mémoire (difficulté de la
méthode matricielle, en particulier) ?
- aura-t-on à refaire plusieurs fois les calculs sur le même graphe (dans le cas par
exemple où les longueurs de certains arcs peuvent être sujettes à modification :
certains algorithmes permettent alors de ne pas recommencer totalement la
procédure) ?