383

PLUS COURT CHEMIN AVEC CONTRAINTES : ALGORITHMES ET APPLICATIONS

par

Michel M I N O U X

A n c i e n ~l~ve de l ' E c o l e P o l y t e c h n i q u e *

RI~SUMI~. - - Le probl~me du plus court chemin avec contrainte suppldmentaire darts un graphe G orientd apparafl dans beaucoup de situations pratiques. Darts les rdseauxx de Tdldcommunications, par e:cemple, les circuits tdldphoniques sont roulds au plus court chemin sous rdserve que l'af[aiblissement lolal le long de ce chemin soit infdrieur ?tune limite donnde. Les mdlhodes lagrangiennes, utilisant la notion de dualitd, permeUent d'obtenir de bonnes solutions approchdes et un encadrement de la solution optimale en se ramcnant ?t la rdso- lution d'une suite de probl~mes de plus courts chemins classiques. Lorsque la solution optimale exacte est recherchde, on montre que l' on peut, sous cerlaines conditions, gdndraliser l' algorithme de Dijkstra (bien connu dans le cas particulier des probl~mes de plus court chemin avec longueurs routes positives). On examine ensuite le cas particulier oft la contrainte suppldmenlaire concerne le nombre d'arcs du chemin. On montre enfin que le probl~me du plus eourl ehemin avec conlrainle est un problkme fondamental de la thdorie des graphes el on

donne plusieurs exxemples de probl~mes qui lui sont dquivalents.

PLAN. - - I. Introduction. II. Formulation du probl~me. I I I . Rdsolution approchde par une mdlhode lagrangienne. IV. Rdsolution exxacte ulilisant un algorithme de Dijkstra gdndralisd. V. Plus court chemin avee eontrainle

sur le hombre d'arcs. VI. Conclusion.

I. I N T R O D U C T I O N

Le probl6rne de la recherche d 'un plus court chernin

entre deux nceuds s et t d 'un graphe G - [X, U]

orientd (*) dont les arcs sont munis de longueurs lu

(pour u G U) est bien connu. Sous rdserve que le

graphe ne contienne pas de circuits de longueur ndga-

t ive (ce que nous supposerons dans toute la suite), il

existe pour le rdsoudre de nornbreux algorithrnes

efficaces [1 h 4].

N6anrnoins, dans un certain nombre de si tuations

prat iques, on recherche ce plus cour t chemin, non

pas parrni l 'ensernble Q de t o u s l e s chernins possibles

(de s h t), mais parmi un sous-ensemble Q' c Q.

Nous 6tudierons plus par t icul i~rement iei le cas oh

ce sous-ensemble Q' est d6fini de la manibre suivante :

ehaque arc u ~ U 6tant rnuni d 'un nombre ~u, Q' est

l 'ensemble des chemins x E Q vdrif iant la relat ion (1) :

(1) E ~.u ~< ~, t tEx

off le second membre ~ cst un nombre donnd.

Dans la suite, nous supposerons que tou t circuit

y de G v6r i f ie : ~ ~u ~> 0 (au t rement dit : il uE~"

n 'exis te pas de circuit de longueur ndgative en fonc-

t ion des nornbres ~u). Cette hypoth~se permct d'affir-

mer que la solution opt imale cst ndcessairement un

chemin dldrnentaire (sans circuit).

Remarquons , d~s main tenant , que pour que Q' ne

soit pas vide, il est n6cessaire de supposer que la lon-

gueur du plus court chemin de s 'h l en fo/action des

hombres ~u (u E U) est infdrieure ou dgale h ~. Dans

route la suite, cet te condit ion sera suppos6e r6alisfe.

Donnons un exemple de tels probl~mes relatif aux

r6seaux de tdl6communications. Dans les r6seaux

t616phoniques urbains, les cent raux sont reli6s entre

eux par des chbles t~ldphoniques de diff6rentes conte-

nances (112 paires, 224 paires, 448 paires...) et de

diffdrents calibres (ill de cuivre de diarn6tre 0,8 mm,

0,6 mm ou 0,4 mm). Comrne le cofit d 'un circuit

t616phonique est proport ionnel h la longueur, le raccor-

dement 6conomiquernent opt imal des cen t raux entre

eux devra i t se faire, logiquement , au plus court chemin

g6ographique. Cependant, il peut arr iver en pra t ique

que ce plus court chemin pr6sente un affaiblissement

total supdrieur aux normes admises (s'il a pour sup-

port des c~bles de calibre trop faible). Le probl~me

est alors de rechercher, parrni t o u s l e s chemins dont

l 'affaiblissernent est inf6rieur h une valeur l imite (donnde), celui dont la longueur gdographique est

minimale.

On sait qu 'un affaiblissernent est un rappor t (entre

la puissance du signal h l 'entrde et ~ la sortie), mais

exprim6 en 6chelle logari thrnique (**), il devient une

* Ingdnieur contractuel au CNET-[ssy, groupement RI~SEAUX ET CENTRES DE COMMUTATION, d6partement I~TUDES EN COMMUTATION ET Rt~SEAUX.

(*) Si le g r a p h e c s t n o n o r i e n t d o n se r a m ~ n e s i m p l e m e n t a u cas p r d c 6 d e n t e n r c m p l a ? a n t c h a q u e a r ~ t c p a r d e u x a r c s d e m ~ m e s c x t r 6 m i t d s , d e m ~ m e s l o n g u e u r s e t d ' o r i e n t a t i o n s o p p o s d e s .

(**) E n d6c ibe l s ( dB) o u e n n d p e r s (N.) .

1/12 A. TEL~C., 30, n ~ 11-12. 1975

384 M . M I N O U X . - - P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S

quaut i td addi t ive ; de sorte que l 'affaiblissement d ' un

chemin peut dtre ddfini comme la somme des affai- blissements des arcs qui le const i tuent . Si :r i> 0

(pour u ~ U) est l 'affaiblissement relatif h l 'arc u,

on recherchera un chemin x ~ Q vdrifiant la contra inte

addit ionnelle (1).

Ce type de probl6mes a ddjh re tenu l ' a t t en t ion de certaius auteurs. Duns [5] par exemple, on dtudie le

cas gdndral off les hombres Ctu et ~ sont de signes

quelconques, sans exclure la possibilitd de circuits ndgatifs (en fonction des hombres :r La mdthode de rdsolution proposde dans [5] ddrivde de la pro- g rammat ion dynamique [6] peut dtre considdrde

comme une gdndralisation de l 'a lgori thme de Bell- man [7] (pour le probl~me du plus court chemin

classique). Cependant , dans les dtudes relatives aux

rdseaux de tdldcommuuicat ions, oh les rdseaux traitds sont souvent de grande taille, ce genre d 'approche

devient vite impraticable. C'est pourquoi nous avons dtd amends h rechercher des mdthodes plus efficaces.

Nous prdsenterons d 'abord une mdthode de rdsolution

approch6e ut i l i sant la not ion de dualitd en program- marion en hombres entiers. Puis une mdthode exacte applicable au cas off les longueurs lu et les nombres :r

sont positifs ou nuls. Enfin, nous parlerons du cas part iculier du plus court chemin avec contraintes sur

le nombre d'arcs (:r - : 1, V u ~ U).

II. F O R M U L A T I O N D U P R O B L ~ ] M E

I I . 1 . Soit G ~ [X, U] un graphe orientd dont les arcs u E U sont munis de longueurs lu:

X = ~1, 2 . . . . . N} est l 'ensemble des nceuds (N = n o m b r e des nceuds),

= {1, 2, ..., M} est l 'ensemble des arcs U (M = hombre des arcs).

Soit A la matr ice d ' ineidence des arcs dans les nceuds de G. Le probl~me du court plus ehemin de s h t est dquivalent au programme lindaire (I) (flot de cofit min imal de s h t et de valeur 1).

I Min ~ lu Xu, u@U

( t ) ) ( 2 ) [AI [x ]~ [b], (3) 0 <~ Xu <~ 1 ( u ~ U ) ,

off x est le M-veeteur de eomposantes xu(u C U) et b u n N-vecteur de composantes bf(i ~ X ) ddfini par :

�9 b i : O ( i : / : s , i ~ = t ) ,

�9 b s = - - l ,

* b t = + l .

Comme la matr ice A est totalement unimodulaire [8, p. 139], la solution optimale x* d ' un probldme de type (I) est toujours enti~re (seconds membres

entiers), le plus court chemin d tant formd par les

* 1 . arcs u tels que x u =

(N. B. dans la suite, on confondra dans une mdme notation un M-vecteur x = (Xl, xe, ..., x i ) h composantes 0 ou 1 et le chemin constitud par les arcs u ~ U tels que xu = I.)

II.2. Le probl6me posd au paragraphe I correspond

h l ' iu t roduet ion de la cont ra in te suppldmentaire :

(1) Z ~u Xu <<. ~. uEU

Si on se contente alors de rdsoudre le probl~me (II) :

(II)

I Min ~ lu Xu , u~U

,(1) Z ~ u X u < ~, u~U

f(2) [A] [x]= [b] , i (3) 0 <. Xu <~ 1 ( u ~ U ) ,

selon les techniques classiques de la p rogrammat ion lindaire, la solution trouvde en gdndral ne sera plus

enti~re : la raison e n e s t que la contra inte (1) ddtruit

l'unimodularitd totale de la matr ice des contraintes de (I). Par suite, notre probl~me est dquivalent au

probl~me en nombres entiers ( I I I ) su ivant :

(III)

' Min ~] lu Xu,

i u@U (1) Z ~u Xu <~ ~ , uEU

I (2) [A] Ix] = [b], (3) 0 ~ X u ~ l ( u ~ U ) ,

e t : (4) Xu entier 0 ou 1 .

II.3. Lorsqu 'on recherche un plus court chemin de s h t duns G, satisfaisant la cont ra in te suppldmen-

taire (1), il est intdressant de commencer par rdduire le graphe G su ivant le priucipe su ivant :

- - o n commence par rechercher les plus courts chemins de s h j ( u : / : s ) et de j h t ( V j :A t) en fonction des nombres ~u (u E U). Soient ~ (s, j ) et ~r (j, t) leurs valeurs.

Alors :

- - si un nceud k C X est tel que :

~ (s, k) + ~ (k, t) > ~ ,

alors on est stir que k n ' appa r t i end ra pus au chemin

optimal cherchd. On peut doric dliminer du graphe G le nceud k et t o u s l e s arcs incidents h k ;

- - si un arc u : (k, l ) ~ U est tel q u e :

(s, k) + ~u + ~ q, t) > ~,

alors on peut dtre stir que u n ' appa r t i end ra pas au chemin optimal cherch6, et on pcut donc l'61iminer du graphe.

I1 suffira donc de rdsoudre le probldme sur le graphe rdduit (c'est un sous-graphe partiel du graphe initial),

A. T~LEC. , 30 , n ~ 1 1 - 1 2 , 1 9 7 5 2112

M. M I N O U X . - P L U S C O U N T C H E M I N A V E C C O N T R A I N T E S 385

d'ofl un gain de t emps de calcul souvent apprdciable. Dans tou te la suite, nous supposerons que eet te

rdduet ion a ~td p r~a lab lemen t effeetu~e ( au t r emen t

dit , que le graphe G donnd est i rrdductible) .

III. R~.SOLUTION APPROCH1~.E PAR UNE MI~.THODE LAGRANGIENNE

Soit Q l ' ensemble des chemins dldmentaires de s h t

dans G - - [X, U]. Pour x ~ Q, notons :

l (x) =

~(x) =

lu , u~x

"~ O~U. U~X

Le probl~me ( I I I ) peu t s 'dcrire de fagon ~quivalente :

! Min l(x) = l(x*) , t ( I l I ) ' ] (1) ~(x) <~ ~ ,

. X @ Q .

III.1. D6finition du probl6me dual.

En associant h (1) un mul t ip l i ca t eu r de Lagrange X ~> O, le probl~me dual (IV) de ( I I I ) est la recherche de X max ima l i s an t la fonction de Lagrange:

i Max L(X) ~ - - X~ + Min {l(x) § X~(x)}, ( I V ) xcO

X ~ t t + ,

Fischer et Shapiro [9]). Pour X /> 0 donnd, calculer L(X) revient h rdsoudre

un probl~me de plus cour t chemin classique de s h t en fonction des longueurs lu § XO~u (u ~ U), soit :

I Min { l ( x ) + X~(x)} . if(X) : xEQ

Remarquons qu 'en ver tu des hypothbses f a r e s au pa rag raphe I, pour tou t circui t y on a :

lu >~ 0 et ~ C(u ) 0

(lu + X Uu) >~ 0 (pourX >~ 0) . u G y

Le p rog ramme dual (IV) poss~de un cer ta in nombre de propri~t~s que nous allons rappeler . Nous mon- t rerons e n s u r e comment ces propridt~s peuven t ~tre utilisdes pour rdsoudre ( I I I ) ' .

III.2. Propri~t~ 1.

Pour tou t X ~> 0, la fonct ion L(X) est une borne inf6rieure de l(x*), op t imum de ( I I I ) . A u t r e m e n t di t : l(x) /> l(x*) >~ L(X) ( V x ~ Q et VX /> 0) .

Ddmonstration.

Pour X o donnd, s o i t :

l(xo) + Xo ~(xo)= Min { l ( x ) + X o ~(x)}. xEQ

On peu t done ~crire :

l(xo) + XoZr ~< l (x*) - - Xo~(X*),

mais pa r d~finit ion de x* on a : c~(x*) <~ ~, &off :

l(xo) § X o~(X0) ~ l ( x * ) § Xo~ ,

et pa r suite : L(~o) ~< l(x*). (C.Q.F.D.)

R~soudre le probl~me dual (IV) revient donc h rechercher la meil leure des bornes infdrieures du t ype L(X).

III.3. Propri6t~ 2.

Pour une va leur X o de X, soit x o ~ Q tel q u e :

l(xo) + X o ~(Xo) = Min {l(x) § X o at(x)}. xEQ

Si on a : ~(xo) = ~, alors : l(x*) -- l(xo) , et x o est une solution op t imale de ( I I I ) ' .

On a en e f fe t :

L(Xo) -- l(xo) § Xo [~(Xo) - - ~] = l(xo).

I1 r6sulte de la propridtd 1 que L(Xo) est solut ion opt imale de (IV) et l(xo) est solution opt imale de ( I I I ) .

III.4. Propri6t6 3.

La fonction de Lagrange L(X) est concave, lin~aire par morceaux.

Ddmonstration.

Pour X >/ 0 donn~, L(X) est le min imum des valeurs prises pa r toutes les fonctions lin~aires :

zx(X) = l(x) + x [~(x) - ~ 1 ,

pour x pa rcou ran t Q, ensemble fini. La fonct ion L(X) est donc l ' enve loppe inf~rieure

de la famille de droites zx(X) darts un plan r appor td aux coordonndes (z, X), d'ofi le rdsul ta t .

A v a n t d '~noncer la propridtd suivante , ddfinissons pour X >~ 0 donnd, x(X) ~ Q comme le plus cour t chemin de s h t en fonction des nombres l u § X~u(U~ U). Soit :

I(~(X)) § X ~ ( x ( X ) ) = Min { l ( x ) + X~(x)}. xEQ

Pour simplifier les notat ions, nous poserons :

~(x) = l ( ~ ( x ) ) ,

e t : ~(X) = ~(x(X)).

Alors :

3/12 A. TI~LEC., 30, n ~ 11-12, 1975

386 M. M I N O U X . -- P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S

III.5. Propri6t6 4.

La fonct ion [ (k ) est monotone croissante de )~ (au sens large) et ~(~) est monotone d6croissante de ), (au sens large).

Ddmonslration.

Dans l ' i n te rva l l c entre deux points de rup tu re de pen te ~,' et X" successifs de L()0, les fonctions ~(~,) et 1 ()0 sont constantes . E tud ions alors leurs var ia t ions au passage d 'un po in t de rup tu re de pente )~'.

Ce po in t est d6fini pa r l ' in tersec t ion des deux droi tes d '6qua t ion :

z -- ~(Z' - - ~) + XE(Z' - - ~) - - ~ ,

z = ~ ( K + ~ ) + ~ ( ~ ' + ~ ) - - Z ~ ,

(pour r > 0 suff isamment pet i t ) . Posons )~]= ~ ' - - r et k 2 = ~ ' + e. Pa r d d f n i t i o n des fonct ions I e t ~, on peu t dcrire :

~(Z~) + (Z' + ~) ~(Z~) /> ]-(Z 2) + (Z' + ~) ~(Z~),

et compte t enu du fa i t que k' vdrifie :

il v i en t : ~ ( ~ ) /> ~0~) ( a ) ,

ce qui pe rme t d 'dcr i re alors :

T(~'I)--TO~2) = k' [ ~ ( ~ ' 2 ) - E ( ~ ' I ) ] ~ O ,

d'ofl : ] - (~ ) ~< ]-(k2) (b) .

Les re la t ions (a) et (b) ddmont rcn t la proposi t ion.

III.6. Exemple.

On pour ra v~rifier les propri~t~s pr~c~dentes sur l ' exemple du graphe de la figure 1. Le premier des

9 ,4~~~"~ , 5

FIG. 1. - - Graphe pris pour exemple.

deux nombres associ6 h chaque arc u e s t sa longueur lu, le second le coefficient gu �9 I1 existe, dans ce cas, qua t re chemins 616mentaires de l 'or igine ~) h l ' ext r6- mit6 ~ et on a r e spec t ivement :

chemin {1, 2, 4} : 1 ( 1 ) = 13 , ~r 14,

chemin {1, 3, 4} : 1 ( 2 ) = 17 , ~r 9,

chemin {1, 2, 3, 4} : l ( 3 ) = 25 , a ( 3 ) = 23,

chemin {1, 3, 2, 4} : l ( 4 ) = 20 , ~r 7.

En supposan t ~ = 10 on a trac~ h la f g u r e 2 les

L(X)

2 0

s , , / ( D ~ )

/ /

..Joo

i f I

i i i i

i i

I

I i

i 0 , 8 1

I t

t ,, i I i

I I I I I

I I

1 , 5

.......... (D2)

FIG. 2. - - Fonction de Lagrange L(;~) dans l'exemple de la figure 1.

qua t re droites cor respondantes d 'dqua t ion :

D(1 ) : z = 13~- 1 4 ~ - - 1 0 ~ ,

D ( 2 ) : z = 17-[- 9 ) ~ - - 1 0 ~ ,

D(3 ) : z = 2 5 + 2 3 ~ - - 1 0 ) ~ ,

D ( 4 ) : z = 2 0 + 7 X - - 1 0 ~ .

La fonction L(k), envelopl)e inf6rieure de ces droites, est concave, l in6aire pa r morceaux, et pr6- sente deux points de rup tu re de pen te pour kl = 0,8 ( intersect ion de D(1) et de D(2)) et pour )~2= 1,5 ( in tersect ion de D(2) et de D(4)).

111.7. R~solution du problbme dual par une m6thode dichotomique.

Rdsoudre le probl~me dual rev ien t h rechercher le m a x i m u m d 'une fonct ion concave, l indaire pa r mor- ceaux, de la var iable )~. La concavi td de L 0 0 assure que t ou t op t imum local est un o p t i m u m global. I1 existe de nombreuses mdthodes d 'op t ima l i sa t ion d 'une fonction h une var iable (mdthode dichotomique, mdthode de Fibonacci , etc.), mais qui ne convergent pas forcdment en un nombre fini d ' i tdra t ions .

Dans la mdthode que nous proposons ici, on recherche la va leur op t imale L0~* ) h l ' a ide d 'un pr in- cipe dichotomique. P a r t a n t d 'un in terva l le [)~1, k2] dont on sait qu ' i l con t ien t ~*, on rddni t progressi- vemen t cet in terval le en u t i l i s a n t : d 'une pa r t la propriEld 4 (monotonici t~ de l ( k ) et ~(~) ) ; d ' au t r e par t , le fa i t que ~* pen t 8tre d6fini p a r l ' in tersec t ion de dcux droites d 'dquat ions : z = l(x 1) § k~(x 1) - - ~

et z = l ( x 2 ) + k0~(x 2 ) - k~ (x 1~ Q , x 2 ~ Q ) .

In i t ia lement , on prend kl = 0 et ks = § oo. La procedure peu t ~tre explicit~e de la fa~on

su ivante :

A. T~LEC., 30, n ~ 11-12, 1975 4/12

M. M I N O U X . -- P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S 387

Procddure 1.

1 ~ R6soudre les probl~mes if(k1) et ff(ke) pour

k 1 - 0 , k 2 = ~- (X).

2 ~ Si ~(+ oo) > ~ FIN : le probl~me ( I I I ) ' n ' a pas

de solution. Si ~(0) ~< ~ FIN : la solution optimale de ( I I I ) '

est le chemin x(0) de longueur 1(0).

3 ~ Soit k' le point d ' intersect ion des droites d '6qua-

t ion :

z = i-(>,~) + x o~(X~) - - x ~ ,

z = ](X2) + X~(X2) - - X[3,

on a : x ' = ( T ( X 2 ) - ~ ( X D ) / ( ~ ( X D - &(x,)) >/ 0 .

4 ~ Fl~soudre le probl~me ff(k').

�9 Si L ( k ' ) = l ( X t ) § X ' ~ ( k l ) - - k ~ - l (X2)+ X~(k2)--X~,

mN : X * - X' e t le chemin ~(%~) es t so lu t ion optimale (ou suboptimale) de ( I I I ) ' . Les deux

valeurs L(k*) et l(X~) fournissent un enca- drement de l ' op t imum de ( I I I ) ' .

�9 Sinon :

5 ~ �9 Si ~(k) > ~, faire X l -- k' et re tourner en 3 o.

�9 Si ~(X) ~< ~, faire ; % - k' et re tourner en 3 ~

La rdsolution de (IV) se ram6ne done h la rdso- lu t ion d ' u n certain nombre de probl6mes de plus courts chemins classiques i f (k)pour des valeurs de k bien ehoisies. La convergence finie de la procddure l vient du f a r que la fonetion L(X) est l 'enveloppe infd-

rieure d 'un nombre fini de droites (ehaque droite

correspond ~ un ehemin dl6mentaire x e Q entre s et t, et Q est un ensemble fini).

Apr6s convergence, on obt ient :

- - u n e solution r6alisable de ( I I I ) ' gdn6ralement optimale ou subopt imale : e'est le ehemin "~(~.2) de longueur l(k2) obtenu comme solution optimale du

probl6me if(k) pour k k2 (par construct ion on a bien ~(k2) ~< ~);

-- un eneadrement de l ' op t imum thdorique l(x*) :

L(?,*) ~< l(x*) ~< ]-(k~).

L 'exemple de la fgure 3 mont re eependant qu' i l

LIM,

L(X*}

x ~,t x" x 2

FIG. 3. - - (]as Ofl la procedure 1 n'aboutit pas /1 l'optimum absolu de (3).

Darts ce cas, la procddure 1 trouve le ehemin de ~(X~) de longueur 1(),~), mais il existe un chemin x ~ Q de longueur l(x) inf6rieure h l(X2) et tel que a ( x ) - ~ ~ 0.

peut exister des cas off la procddure 1 n ' a bou t i t pas h l ' op t imum absolu de ( I I I ) ' . Ainsi le chemin x ~ Q est tel q u e :

L(X*) < l(x) + X*[~(x) - - ~1

et pour t an t on a : l(x) <]-(k2) et ~ ( x ) - - ~ ~< 0. La diffdrence l ( x ) § k * [ ~ ( x ) - ~ ] - L ( k * ) > 0 est

appel6e le saut primal-dual (duali ty gap). Sa valeur

eonsti tue une bonne mesure de la difficult6 du pro- blame ( I I I ) ' .

Terminons en s ignalant que la valeur optimale du dual L(k*) peut 6videmment servir eomme fonetion d '6valuat ion minoran te dans une procddure de recherche arborescente (S.E.P. ou Branch and bound).

Cependant, pour les probl~mes prat iques qui nous intdressent, ce genre d 'approche a 6t6 6cart6, ear cela eonduirai t ~ des temps de rdsolution prohibitifs.

III.8. Exemple.

Le fonct ionnement de la procddure 1 peut ~tre

illustr6 sur l 'exemple de la figure 1, pour lequel on a pris ~ = 10.

Pour k - - 0, on obt ient ] - (0)= 13 et ~ ( 0 ) = 14. Pour k = § cx~, [ ( + o Q ) = 20 et ~(§ cx))= 7. Le point d ' intersect ion des deux droites :

z 1 - 1 3 + 4 k et z~= 2 0 - - 3 k

a pour abscisse k ' - - 1 (Fig. 2).

La rdsolution du probl6me if(k)' fourni t alors le chemin {1, 3, 4} pour lequel f ( 1 ) = 17 et ~ ( 1 ) = 9.

Comme on a : L ( 1 ) = 16 < 17, l ' op t imum n 'es t

pas encore at te int .

Puisque ~(1)-- 9 ~< ~, on pose k2-- 1 et l ' in ter - valle [k l , k2] devient [0, 1].

L ' intersect ion des deux droites d '6quat ion :

z 1 = 1 3 + 4 k et z2-- 1 7 - - X

donne alors le point X ' = 4/5. Cette fois, on a b i e n :

L(k') = 81/5 -- 17 - - X' = 13 + 4 X'.

D o n e : k * = k ' = 4[5. La procddure 1 fourni t alors pour k 2 = 1 le chemin

x(k2) = x ( 1 ) = {1, 3, 4} de longueur 17 et v6rif iant ~(1) 9 < ~.

On obt ient aussi l ' encadrement :

L(k*) - - 16,2 ~< l(x*) ~< 17 l (k2) .

ce qui montre que la solution optimale est bien ici le chemin {1, 3, 4} de longueur 17.

III.9. G6n6ralisation au cas de plusieurs contraintes.

L'approche que nous avons consid6r6e ici se g~n6-

ralise h u n nombre quelconque p > 1 de eontra intes de type (1) (toujours sous t 'hypoth~se qu'i l n 'existe

5/12 A. TI~LEa., 30, n ~ 11412, 1975

388 M. M I N O U X . - P L U S C O U R T C H E M I N A V E C C O N T B A I N T E S

pas de circuits n6gatifs en fonction des nombres ~tu). E n associant des mult ipl icateurs de Lagrange (varia- bles duales) k~, )~ . . . . . Xv 1> O h chacune de ces contraintes, on d~finit une fonction de Lagrange

L0,~, k2, ..., kv) concave et non par tou t diff6rentiable.

Pour rechercher le m a x i m u m de L(X0 on doit alors

utiliser :

- - soit la p rogrammat ion lin6aire [9, 10],

- - soit une m6thode de sous-gradient [11].

Contra i rement au cas p = 1, on n'est plus certain, avec ces mdthodes, de trouver une solution rdalisable (c'est-~-dire v6rif iant routes les contraintes suppl6- mentaires), mdme s'il en existe une.

Notre expdrience pra t ique sur des probl6mes ana-

logues ([12] par exemple) indique cependant que l 'on obt ient g6ndralement par ces m6thodes :

- - des solutions rdalisables proches de l ' op t imum,

- - un bon encadremeut de l 'op t imum.

Signalons, pour finir, que les mult ipl icateurs opti- * (ou des valeurs approch6es maux k* , )~ . . . . . )'v

de ceux-ci) sont tr6s int6ressants pour r6duire le graphe G avan t de recourir h une m6thode de r6so-

lut ion exacte (Branch and bound, ou algorithme de Dijkstra g6n6ralis6; cf. chap. IV). I1 suffit de cons-

t ruire la contraiute combinaison lin6aire h coefficients : * * *

; ~ , ),2 . . . . , k v des p contraintes in i t ia les ; puis de rdduire le graphe par la mdthode indiqu6e au para-

graphe II.3 en u t i l i sant cette contra inte supplfimen-

taire. Comme cette contra inte est, en un certain sens, la plus forte de toutes les contraintes obtenues par combinaisons lindaires des contraintes initiales [13, 14], la r6duction ainsi effectnde est quasi optimale.

IV. I:t]~SOLUTION EXACTE U T I L I S A N T

UN A L G O R I T H M E DE D I J K S T B A G~.N]~RALIS]~

Nous donnons, dans ce chapitre, une m~thode de r~solution exacte p e r m e t t a n t de calculer simultanfi- men t tous les plus courts chemins d'origine s dans G satisfaisant la cont ra in te :

uEU

[donc, en particulier, le plus court chemin de s h t

satisfaisant la cont ra in te (1)].

Cette m6thode [15] est une extension de l 'algo-

r i thme de Dijkstra [4], bien connu darts le cas part i- culier du plus court chemin ordinaire avec longueurs positives ou nulles. Elle constitue, par cons6quent, une am61ioration de l 'a lgori thme proposd par Joksch dans [5] (ce dernier pouvan t ~tre consid~rd comme un algori thme de Bellman [7] gdn~ralisd).

IV.i . Hypothbses.

Nous ferons deux hypotheses (peu restrictives en

prat ique) :

- - les longueurs lu (u E U) sont des nombres r6els

/ > 0 ;

les hombres ~u sont des nombres ~> O;

- - pour tou t circuit 616mentaire y de G, on a :

~ > 0 . uEy

On notera 0~min le m i n i m u m de toutes les quant i tds ~u sur l 'ensemble des circuits 6Idmentaires de G.

uE7 On a donc 0~min > 0 .

Nous commencerons par supposer provisoirement

que le nombre ~l est un entier > O et que les gu sont

des entiers /> O (nous verrons au w IV.5 comment on peut se d6barrasser de cette hypoth6se).

IV.2. Extension du principe d'optimalit6 et marquage multidimensionnel.

Le principe des algorithmes de Bel lman [7], Ford [6]

et Di jkst ra [4] est d'affecter h chaque sommet j ~ X un nombre rz(j) (une marque) (au d6but : x(s) = 0 ;

x( j ) = + o0 VJ r s) et d'am61iorer i t6ra t ivemeut ces

valeurs jusqu 'h ce que 7:(j) repr6sente la longneur du plus court chemin de s h j (Vj =/: s).

Le succ~s de toutes ces mdthodes rdside dans le

principe d'optimalitd [6] : si Xsj est uu chemin optimal entre s e t j e t si l 'arc (k, j ) est le dernier arc de ce

chemin, alors le sous-chemin Xsk est un chemin optimal entre s et k.

Dans le cas du plus court chemin avec contra inte suppMmentaire, le principe d 'opt imal i t6 doit ~tre modifi6 de la fa~on suivante : si Xsj est le plus court chemin de s h j v~rifiant : ~ ~ u = ~1 ~< ~ et si

u~xsl v = (k, j ) est le dernier arc de ce chemin, alors le

sous-chemin Xs~ est le plus court chemin de s fi k vf i r i f iant : ~ ~ u = ~ l - - a v .

UEXslr Par suite, on doit marquer chaque sommet j ~ X,

non plus h l 'aide d 'une quant i t6 scalaire (comme dans le cas du plus court chemin classique), mais en uti- l isant un vecteur h ~ § I composantes :

~:(j) = [Zoo(j) tel(j) . . . rc~(j)]

(marque mult idimensionneIle) . On recherche alors une proc6dure de marquage au

terme de laquelle Yk (0 ~< k ~< ~)7~k(j) reprdsente

la longueur du plus court chemin xsl de s h j vdrifiant :

E ~ u = k. u~xs t

IV.3. Une algbbre du plus court chemin avec contrainte.

Comme dans [15], notons S l 'ensemble des vecteurs h ~ + 1 composantes darts R + U ( + oo}. S est muni

A. T~LEC., 30, n ~ 11-12, 1975 6/12

M. M I N O U X . -- P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S 389

d ' u n e op6ra t ion in t e rne @ d6finie p a r :

a = (a0, a 1 . . . . . a~) b (bo, b 1 . . . . . b~)

c = a @ b - - (Co,C 1 , . . . , c ~ ) a v e c :

Cr-- m i n { a r , b r } , V r - - 0 , 1 . . . . . ~.

L ' d l 6 m e n t n e u t r e de @ est z ( + ~ , + ~ . . . . . + ~ ) .

On vdrif ie que a ( ~ ) a = a ( V a ~ S ) : l ' opd ra t i on @

est idempotente.

A c h a q u e arc u = (i, j ) ~ U on associe l ' a p p l i c a t i o n

h 0. de S---> S ddfinie p a r :

htj(% , a 1 . . . . . a~) (b o , b 1 . . . . . b~),

oil b r - + oo p o u r r < ~ u ,

e t : br -- ar' + lu p o u r r /> ~u (off r ' -- r - - ~u).

I1 est faci le de vdr i f ier que, pour t o u t arc : u- - ( i , j )~ U,

l ' a p p l i c a t i o n h~. est un endomorphisme de S, c ' es t -h-

dire que :

h~](a @ b ) - - h~](a) @ hi](b) (Va ~ S, Vb ~ S).

On n o t e H l ' e n s e m b l e des e n d o m o r p h i s m e s ho. :

" = {h~jl( i , j ) ~ U } .

On d6signe pa r h ~ l ' e n d o m o r p h i s m e de S tel que :

h~(a) = ~ (Va ~ S).

On r e m a r q u e alors que les e n d o m o r p h i s m e s de H

son t K-stables au sens de [15], c ' es t -~-d i re q u e :

Vh 1 , h 2 , . . . , h K ~ H on a :

hi,: 0 hK-~ 0 ..... 0 h a 0 h z = h a .

I1 suffit p o u r cela de ehois i r : K > N [ ( ~ [ O ~ m i n ) + l ] + N .

E n effet, t o u t c h e m i n x e m p r u n t a n t au moins

[(~/~min) + 1] fois un c i rcu i t d l~menta i re q u e l c o n q u e

du g raphe sera tel q u e : ~ ~uXu > ~ (Xu est le uGU

n o m b r e de lois que le c h e m i n x e m p r u n t e l ' a rc u).

C o m m e un c i rcu i t 616mentaire a au plus N arcs,

ce sera le cas de t o u t c h e m i n c o m p t a n t plus de

N [ ( ~ [ 0 ~ m i n ) ~ ] - 1 ] - - *)~" arcs.

Ce t te propr id td p e r m e t d ' d t ab l i r la c o n v e r g e n c e des

a lgo r i t hmes de B e l l m a n et de F o r d c o n v e n a b l e m e n t

g6n6ralis6s [15].

I V . 4 . P r e m i e r a l g o r i t h m e de D i j k s t r a g 6 n 6 -

r a l i s 6 .

Cependan t , dans le cas qui nous int6resse, on p e u t

encore amdl iore r l ' a l g o r i t h m e de F o r d gdn~ralisd en

r e m a r q u a n t que l ' on p e u t ddfinir dans S la r e l a t ion

de prdordre total :

(a o , a 1 , . . . , a~) ~ (bo, b 1 . . . . . b~) ~

Min (ar} <~ Min ( b r } , ~=0,...~ r=0,. . .~

qui poss6de les deux propr id tds s u i v a n t e s :

c~_ a et c ~ b ~ e ~ a @ b (Va, b, c c S )

e t : hij(a) 3O_ a Vh~] E H et Y a ~ S .

C o m m e on recherche , p o u r c h a q u e nceud j c X,

une m a r q u e min ima le (*) darts S ( m i n i m a l e au sens

de la r e l a t ion de pr~ordre ~ ) , on p e u t e m p l o y e r [15]

l ' a l g o r i t h m e de D i j k s t r a g~n6ralisd :

A l g o r i t h m e ( ,41) (O:u ent ie rs /> 0).

1) I t 6 ra t ion k = 0.

~(s) (0, + ~ , + ~ , ..., + o o ) .

7:(j) = r V j V- s .

x , : o {s}. 2) I t e r a t i o n k k § 1.

Choisir m ~ X 2 c X v ~ r i f i a n t :

x ( m ) ~ ( j ) V j ~ X 2 ,

3) X , = X 1 U ( m } ,

4) Si X 1 -~ X, FIN : les m a r q u e s r:( j) son t min i -

m a l t s (dans S) p o u r t o u s l e s j ~ X, s inon :

5) p o u r t o u s l e s arcs (re, j ) c U :

�9 ca lcu le r x ' ( j ) = x ( j ) @ hmj(z~(m)) .

�9 S i n ' ( j ) # x ( j ) , p o s e r : X 2 = X 2 U { j }

et fa i re x ( j ) = x ' ( j ) .

6) Si X 2 = O, fin de l ' a l g o r i t h m e , s inon r e t o u r n e r

en 2).

[N. B. : si on ddsire seulement le plus court chemin de s h t (t donnd), il sufflt de s 'arr~ter h l 'dtape 4) lorsque t G X~.]

C o m m e dans l ' a l g o r i t h m e de D i j k s t r a c lass ique [4],

X z c X reprdsen te l ' e n s e m b l e des nceuds p o u r les-

quels le plus c o u r t c h e m i n ( sa t i s fa i san t la con t r a in t e )

a 6td t r o u v 6 ; X 2 c X reprdsen te l ' e n s e m b l e des

nceuds j ~ X pour lesquels la m a r q u e x ( j ) a 6t6

modif i6e depuis le dern ie r passage h l ' 6 t ape 5) ; p o u r

ces nceuds, le plus cou r t c h e m i n n ' a pas encore 6t6

t rouv6.

C e p e n d a n t , on n ' a pas X 1 (3 X 2 ~ 0 ( c o m m e dans

l ' a l g o r i t h m e de D i j k s t r a c lass ique) h c h a q u e i t6 ra t ion ,

et pa r consdquen t (A 1) conve rge gdn6ra l emen t en plus de N i tdra t ions . L ' a v a n t a g e de l ' a l g o r i t h m e (A 1)

sur celui propos6 dans [5] rdside darts les r e m a r q u e s

su ivan t e s :

a) dans [5], on calcule tous les plus courts chemins

p o u r routes les valeurs O, 1, 2 . . . . , ~ possibles du p r e m i e r

m e m b r e de (1), en t r e s e t j (Vj ~ X). A u t r e m e n t dit ,

on n 'a r r f i te pas le m a r q u a g e t a n t que 7 : i ( j ) n e reprd-

sen te pas e f f e c t i v e m e n t la l ongueu r du plus c o u r t

c h e m i n d ' a f f a ib l i s semen t i en t re s et j (V j et Vi).

b) darts l ' a l g o r i t h m e (A 1) au con t ra i re , l o r s q u ' o n

t ransf6re p o u r la premi6re fois dans X 1 un nceud

(*) Puisque ~ est une relation de prdordre, l'616ment minimal d'un sous-ensemble tint de S n'est g6n~ralement pas unique.

7/12 A. TI~LEC., 30, n ~ 11-12, 1975

390 M. MINOUX. - PLUS COURT CHEMIN AVEC CONTRAINTES

j �9 X quelconque, la plus pet i te composante de x( j ) reprdsente bien la longueur du plus court chemin satisfaisant la contra inte (1) entre s et j ; mais il n 'es t pas n6cessaire que les autres composantes repr6sentent effectivement des plus courts chemins. Le nombre de

marquages effectud par l 'a lgori thme (A 1) est donc, g~n~ralement, tr~s infdrieur.

IV.5. Second algorithme de Dijkstra g6n6- ralis6.

L'algor i thme (A 1) sous cette forme est encore susceptible de quelques am5liorations techniques.

On remarque d 'abord qu' i l est inuti le de conserver en mdmoire les composantes des marques r:(j) qui

restent ~gales fi + oo. On remplacera donc chacune des marques x( j ) par une lime L 1 de v I couples :

(t~}, a}) v = 1, ..., v~

correspondant chaeun fi un chemin entre s e t j .

p~ est la longueur du v e chemin x, (1 ~< v ~< vj)

et a } = Z ~u u�9

(ceci revient f i n e consid~rer que les chemins efficaces au sens de [5]).

Supposons que la liste Lj soit telle qu'i l existe v, et v~ v~r i f i an t : ~}~ ~< ~ et ~ ~< ~ . Alors le chemin v2 de la liste ne pourra jamais faire part ie d ' un chemin optimal, et par suite, le couple v~ peut

~tre 6limin6 de la liste L I .

L 'op6rat ion prdc~dente, rdpdt~e sur tous les cou- ples vl et v~ s 'appelle la rdduclion de la liste L j . La

nouvelle liste obtenue est notde L 1 (liste r6duite).

Une liste sera dite irrdduclible s i : L / = L I .

Une liste L i irrdductible est donc ndcessairement

telle que :

( ~ #~ (~'~ (Vvl , v~ = 1 . . . . . v.~, v 1 v ~ v~.

On voit que l 'on peut , ma in t enan t , lever la restric- t ion sur l ' intdgri t6 des nombres ~tu et ~ faite en IV.1. Dans ce qui suit, ~ les :tu seronl donc des nombres r&ls >~ 0 quelconques.

D~signons par s l 'ensemble des listes irrdductibles finies de couples (i~,6), off f l � 9 + , ~ s R +. E t a n t

donn6 deux listes L 1 et L2 �9 ~ :

~ = {(~;, ~;) ~ = ~ . . . . . ~ 1 } ,

~ = {(~;, ~;) ~ = ~ . . . . . ~} ,

d~finissons l 'opdrat ion rdunion (U) p a r :

L , ~ L~ = {(~ , ~ ) ~ = 1 . . . . , ~} ,

avec v~= v , + v~ e t :

( f l~ ,~ ] )= (p~,a~) pour v = 1 . . . . . v l ,

et : (fl], (r~) = ( p ( , ~ ' ) pour v = vl + 1 . . . . . v~ + v=,

e t : v ' = v - - v 1.

L'ensemble s sera alors mun i de l 'op~rat ion @ dfifinie par :

L 1 @ L2 = (L 1 U L2) (rdunion + rdduetion).

On v6rifie que @ est idempotente. L'dMment neutre est la liste vide {0} not6e r A chaque are u = (i, j ) de G assoeions l 'appl icat ion

flj de s - + g d6finie p a r :

q = { ( p ~ , ~ ) ~ = ~ ..... ~}, |

f,;(r,) = L2 = Z f,;{(~, ~;)} V = I , . . . V 1

@

(~, ddsigne la sommat ion au sens de l 'opdrat ion @)

a ve c : flj {(p; , a;)} = {(~1 + lu , (~; + ~u)} ,

si z~ + ~u ~<

e t : fis (P~,a~) = z s i : a l + a u > ~ .

Les fq sont des endomorphismes de E (Vu = ( i , j ) ~ U). On note f~ l ' endomorphisme tel q u e :

f f f L ) = z VL e s

Comme en IV.4 dfifinissons dans ~ la relation de pr~ordre total :

L1 = { ( p ; , ~ ) ~ = 1 . . . ~ , } L , = { ( p ~ , 4 ) ~ = 1 ... ~,}

L l O C L 2 ~ Min {p~} ~< Min {p~} V = i . . . V 1 V - - I . . . V 2

qui poss~de les propri~tds :

L a__~ L 1 et L a_~ L~ ~ L a ~ L 1 Q L 2,

et : L1 ~ fi1( LO ( V ( i, j ) ~ U) .

On peut alors rechercher tous les plus courts chemins de s aux autres nceuds de G, satisfaisant la

cont ra in te (1) fi l 'aide de l 'a lgori thme de Dijkstra

g~n~ralisd :

A l g o r i t h m e ( A 2 ) (Ctu r6els >/ 0 queleonques).

1) I t d r a t i o n k = 0.

L j = ~ ( V j � 9

x l = o x~:= {s} 2)

( V j � 9 % s ) ,

I t6rat ion k =: k + 1.

Soit m ~ X 2 v6rifiant Lm oC Lj (V j �9 X 2) �9

3) X i = X 1 U { m } .

X2-- X,, - - { m } .

4) Si X~ = X FIN: les listes Lj sont minimales

(dans ~) et l'61dment min imal de ehaque liste L i donne le plus court ehemin entre s et j , satis-

faisant la eontra inte (1).

5) Pour t o u s l e s ares (re, j ) ~ U :

�9 ealculer L} = Lj @ fmj(Am),

�9 calculer A s = L ~ - L j ,

�9 s i A s :/= z, poser : L s = Lj e t : X~ = X z U { j } .

A m ~ E.

6) Si X~ = 0 FIN.

A. T~LEC., 30, n o. 11-12, 1975 8/12

M. M I N O U X . -- P L U S C O U R T C H E M I N A V E ( ] ( ] O N T R A I N T E S 391

Sinon re tourner en 2).

IN. B. : si on ddsire seulement le plus court chemin de s h t (t donnd), il suffit de s'arrSter h l '6tape 4) d6s que t ~ X 1 . ]

Les listes par t ie l les Aj sont utilis6es pour 4viter des marquages inutiles.

Pla~ons-nous par exemple ~ l ' i t6 ra t ion k, off le nmud m ~ X est choisi en 2) comme origine du

marquage. Pa rmi les i t6ra t ions ant6rieures, soit k ' < k, la

derni6re i t6rat ion off le nceud m a 6t6 choisi en 2) comme origine du marquage . Alors Am repr6sente les nouveaux 616ments ajout6s dans la l is te Lm entre les i t6rat ions k ' § 1 et k. Comme G est idempoten te , on remarque q u e :

L'j -- Lj ~ fmy(Lm) -- Lj (~ fmj(Am)

et par cons6quent, il suffit pour marquer le noeud j, de chereher l'image de la liste partielle Am par l'endomorphisme fray.

En pra t ique , comme Aj c Lj il suffit de rep6rer pa r un poin teur les 616ments de la l is te L;- qui sont dans A;. (ef. exemple IV.6).

IV.6. Exemple.

Le fonc t ionnement de l ' a lgor i thme (A 2) sera il lnstr6 sur le graphe de la figure 4, off les nombres

10,4

FIG. 4. - - Graphe ~ 6 noeuds pris comme exemple pour illustrer l'algorithme de Dijkstra g6n6ralis6. On cherche un plus court chemin de s = 1 h t = 6 en prenant ~ = 12.

lu et au sont indiqu4s (dans cet ordre) sur chacun des arcs. On recherche un plus cour t chemin de s = 1 h t = 6 avec ~ - - 12.

On indique le d6tail des i t6rat ions effectu6es pa r l ' a lgor i thme (A 2). Remarque r la par t icu la r i t6 :

X 1 (~ X o ~- O

(h l ' i t6 ra t ion 5), qui dis t ingue (A 2) de l ' a lgor i thme de Di jks t r a classique.

[N. B. : on a convenu de rep6rer les 616merits Aj d'une liste L j e n les soulignant; exemple :

L 4 = {(4,3) (6,2) (9,1)} indique que A 4 -- ((9,1)} . . . . ].

Ildralion O.

{(o, o)},

L ~ = L 3 . . . . . L e : { O } ,

x l : o {1} Itdration 1.

On a : m = 1, , X 1 = {1} , X a = O .

L 2 = { ( 3 , 5 ) } ,

= {(8, 2)},

= {(5, 6)},

X 2 = {2, 3, 4} ,

Iteration 2.

On a : m = 2 (le plus cour t chemin entre 1 et 2 sa t is fa isant la con t ra in te est l ' a rc direct (1, 2)).

X1-- {1, 2} X2- - {3, 4} ,

L 3 - {(8, 2) , (5, 8)} ,

L5 = {(9, 7)} ,

X~= {3, 4, 5} ,

{(3, 5)}. Itdration 3.

On t rouve m = 3 (le plus court chemin de 1 h 3 sa t i s fa isant la con t ra in te passe pa r les nceuds 1, 2, 3).

x,= {1,2,3} {4,5}, L 4 = {(5, 6 ) , (15, 7 ) , (12, 13)} = {(5, 6)} (apr6s

rdduction) ,

L 5 - {(9, 7) , (10, 6) , (7, 12)} (pas de rdduct ion possible) ,

Lo = {(12, n ) } ,

X~-- {4, 5, 6} ,

L a = {(8, 2 ) , (5, 8)}.

Itdration 4.

On t rouve m = 4 (le plus cour t chemin entre 1 et 4 sa t i s fa isant la eon t ra in te est l ' a rc direct (1, 4)) .

XI= {1, 2, 3, 4 } X2= {5,6},

L 3 = {(8, 2) , (5, 8) , (6, 7)} (pas de r6duction),

L s - {(12, 11 ) , (15, 10)},

X 2- { 3 , 5 , 6 } ,

L , - - {(5, 6)}.

Iteration 5.

On t rouve m = 3 (le nceud 3 est de nouveau choisi comme origine du marquage , bien que le plus cour t chemin d6finit if entre 1 et 3 a i t d6jh 4t6 t rouv6 h l ' i t6 ra t ion 3. C'est ici que r6side la diff6rence essen- tielle avec l ' a lgor i thme de Di jks t ra elassique, car on

n ' a pas X 1 N X 2 = 0).

X1-- {1, 2, 3, 4 } X ~ = {5, 6} ,

L a = {(5, 6 ) , (13, 12)} = {(5, 6)} (apr6s r6duction) ,

L 5 = {(9, 7 ) , (10, 6 ) , ( 7 , 12) , (8, 11)} (pas de r6duction) ,

9/12 A. TELEC., 30, n o. 11-12, 1975

392 M. M I N O U X . -- P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S

L 6 = {(12, 11 ) , (15, 10)},

{5, 6}, L~ = {(s, 2), (5, S), (6, 7)}.

Ildration 6.

On t rouve : m = 5 (le plus cour t chemin entre 1 et 5 et sa t i s fa isant la con t ra in te passe pa r les nceuds 1, 2 , 3 , 5 ) .

X 1 : { 1 , 2 , 3 , 4 , 5 } X 2 = {6 } ,

L 6 = {(12, 11 ) , (15, 10 ) , (14, 10 ) , (15, 9)} , d ' o f i :

L 6 = {(12, 11) , (14, 10) , (15, 9)} (apr~s r6duction),

{6}, L 5 = {(9, 7) , (10, 6) , (7, 12) , (8, 11)}.

Irritation 7.

On t rouve m = 6 (le plus cour t chemin entre 1 et 6

sa t i s fa isant la con t ra in te a pour longueur 12 et passe pa r les nceuds (1, 3, 6)) . FIN.

(Noter que le plus cour t chemin sans con t ra in te a pour longueur 10 et passe pa r 1, 4, 3, 6.)

IV.7. Heuristiques dfriv6es de l'algorithme (A 2).

Lorsque le g raphe G est de grandes dimensions (N > 50, M > 100) et qu ' i l n ' es t pas possible de le

r6duire (w II.3), la tai l le des l istes Lj peu t augmente r cons id6rablement (d'ofl un probl~me d ' encombremen t de m6moire sur ca lcu la teur 61ectronique).

Cepcndant , il est in t6ressant de signaler qu 'on peu t d6duire de l ' a lgor i thme (A 2) une famille de bonnes heuris t iques en l im i t an t a rb i t r a i r emen t h un nombre m a x i m u m q donn6 la tai l le des l istes L : . Lorsqu 'h la suite d 'un marquage , une l iste Lj d6passe q 616- ments , on d6cidera de re teni r les q premiers 616ments (p~a~) dans l 'o rdre des ~ croissants. On s 'assure ainsi de pouvoi r t rouver une solut ion admissible s 'il en existe une (il suffit pour cela que q ~> 1). Ev idemmen t , la quali t6 du r6sul ta t fourni est d ' a u t a n t meil leure que q est plus grand.

IV.8. G6nfralisation h un nombre quelconque de contraintes.

La g6n6ralisat ion de l ' a lgor i thme (A 2) h p cont ra in tes de type (1) (p > 1) ne pose pas de difficultd de pr in- cipe. N6anmoins le t emps de calcul et l ' encombremen t en m6moire augmen ten t trbs r i t e en fonction de p, ce qui en l imi te les appl ica t ions h p ~ 2 ou 3 en pra- t ique. Dans t o u s l e s cas, la rdduct ion pr6alable du graphe s ' impose (ut i l isa t ion des mul t ip l ica teurs de Lagrange op t imaux , voir w III .9) .

IV.9. Cas oh ~u ~< 0 et P ~< 0.

Dans le cas off certains des hombres c~u et ~ sont n6gatifs ou nuls, l ' a lgor i thme (A 2) ne peu t plus s 'appl iquer . I1 faut alors se con ten te r d ' un a lgor i thme de Ford g6n6ralis6 [15]. C'est ce qui se produi t , en par t icul ier , lorsque la con t ra in te suppl6menta i re est de la forme :

' X ~' ~ 0~u u / > ,

u E U

avec ~ ~> 0 et ~' > 0 .

Remarquons alors que la solut ion op t imale du pro- bl6me ( I I I ) n 'es t plus ndcessairement un chemin dldmentaire. Si on recherche, de plus, un chemin dldmentaire, le problbme devien t tr~s complexe et on ne connai t pas, ac tuel lement , de bon a lgor i thme pour le r6soudre. (Lorsque ~u = - - 1 (Vu) et ~ = - - (N - - 1) le probl6me est celui du chemin hami l ton ien de longueur minimale entre s et t).

V. P L U S C O U R T C H E M I N A V E C C O N T I ~ A I N T E

SUB LE NOMBBE D'ARCS

Ce cas par t icu l ie r est celui off :

~u= l ( u

et off ~ est un nombre ent ier compris entre 0 et N - 1.

V.1. Si on recherche les plus courts chemins avec cont ra in te entre une origine s el tous les noeuds du graphe, on peu t app l iquer l ' a lgor i thme ( A 2 ) du chapi t re prdcddent (dans ce cas, les ~u d tan t des nombres entiers, la convergence est tr~s rapide).

V.2. Si on recherche tousles plus courts chemins de i ~ j ( V i E X V j E X i # j ) dans le graphe satis- fa isant la con t ra in te (1), on peu t ut i l iser la m6thode des mul t ip l ica t ions matr ic ie l les [16].

D6signons par [D] = [d/j]i=l...N ~=I. . . /V

la matrice d'adjacence gdndralisde du graphe G au de [15] et d6finissons dans R+ U { + o0} les sens

op6rat ions @ et ~ :

a @ b = min { a , b } ,

a . b = a + b .

Les opdrat ions @ et . induisent , sur l ' ensemble des matr ices carr6es N • N h coefficients dans R + O { + ~ } les op6rat ions :

[D] = [do. ] [D'] = [d~j],

[D] @ [D'] = [d,';] avec d " = { ' } ~1 min d l : ; d i : , (i)

,, d ,?_ [D] ~ [ D r ] = [d#] avec t ; - - Z d i g ~ - d~i. k

A. T~LEC., 30, n ~ 11-12, 1975 10/12

M. M I N O U X . P L U S C O U R T C H E M I N A V E C C O N T R A I N T E S 393

Soit [D]k= [d,]]i=~...N la puissance k e de la matr ice ] ~ I . . . N

D (matrice d 'adjacence g6n6ralis6e de G) :

[Dlk = [D] ~ [DI * ... * [D] (k lois).

Alors [17] le te rme d~'i �9 repr~sente la longueur du

plus court ehemin de k arcs (exac tement entre) i e t j .

Pour rdsoudre le probl~me posd, il suflira done de

ealculer successivement [D] ~, [D] a . . . . , [D] ~.

Le plus court chemin entre i et j (Vie X, Vj ~ X)

et compor tan t ~ arcs au plus, est alors obtenu en

recherehant le min imum des quanti t~s :

d~j d~] d a.. f~ , , ~ , ..., d i i .

VI. CONCLUSION

Le probl~me du plus court chemin avec contrainte(s)

suppldmentaire(s) est un probl~me fondamenta l en

th6orie des graphes. I1 apparai t , comme nous l ' avons

dit, dans beaucoup d 'appl icat ions prat iques, par

exemple darts les dtudes dconomiques relat ives aux

r6seaux des td l@ommunicat ions (chap. I). De plus,

nous allons voir que certaines classes impor tantes de

probl~mes peuven t se ramener h des probl~mes de

plus courts chemins avec contraintes.

On recherche ensuite un plus court chemin de s

h t, sur lequel la somme des invest issements n 'excbde

pas G. On peut utiliser l ' a lgor i thme (A 2) du cha-

pitre IV.

VI.2. Un probl~me d'ordonnancement.

On sait qu 'un probl~me d 'o rdonnaneement clas-

sique peut se ramener h la recherche d 'un plus long

chemin (chemin crit ique) dans un graphe sans circuit.

La longueur d 'un arc est dgale h la duroc de la tfiche

associde. On suppose ici que l 'on peut, grfice h des

invest issements suppl6mentaires, diminuer la durde de

certaines tfiches. Ce probl~me a dt~ dtudi6 dans le

cas lin6aire continu (off les durdes d~croissent lindai-

rement en fonction des invest issements effectu~s) et

on a pu mont re r [18] qu' i l se ram~ne alors h u n

probl~me de riot h coflt minimal.

Dans le cas discret (off les durdes sont des fonctions

en escalier des investissements), en effectuant une

t ransformat ion analogue h celle du w VI-1, on se ram~ne

h la ddterminat ion d 'un chemin cri t ique de longueur

minimale sous la contrainte que la somme des inves-

t issements sur le chemin ne doit pas exc6der une

valeur donn~e.

VIA. ContrSle optimal discret et plus courts chemins.

Le graphe G ~ [X, U] est muui de longueurs

lu(u E U). On suppose que l 'on peut diminuer la

longueur de certains arcs par des invest issements

approprids. Par exemple, pour l 'arc u, on peut dimi-

nuer sa longueur de ~lu h condit ion de ddpenser

gl u francs, de 82u h condit ion de d@enser g2 u francs, etc.

Par ailleurs, une contra inte budg6taire est imposde :

on ne peut d6penser en tout plus de G francs. Le

problbme est de savoir combien il faut d6penser, et

sur quels arcs, pour minimaliser la longueur du plus

court chemin entre s e t t ( s E X , t G X ) , tou t en respectant la contra inte budg6taire.

Ce problbme, qui peut 6tre considdr6 comme la

recherche d 'un contr6le optimal discret (les variables

de contr61e sont les diff~rents invest issements pos-

sibles sur les diff6rents arcs), peut se formuler comme

la recherche d 'un plus court chemin avec contraiute.

I1 suffit, pour cela, de remplacer chaque arc u par

plusieurs arcs de m~mes extr~mit~s :

- - l e 1 er, de longueur lu, associ~ h l ' investisse-

men t 0 ;

- - l e 2% de longueur lu--31u, associd h l ' inves-

t i ssement 9u ~ ;

- - l e 3 e, de longueur lu- -32u, associd ~ l ' inves-

t i ssement g~u.

etc.

VI.3. Extension optimale d'un r6seau existant (cas p l a n a i r e ) .

Soit un graphe G = [X, U] dont les arcs sont

munis de capacitds cu(u E U). On cherche h faire

cireuler, sur ee graphe, un riot entre s e t t (s ~ X, t ~ X),

de valeur supdrieure h la valeur du riot maximal . Pour

cela, on suppose qu 'on peut, par des invest issements

suppldmentaires, augmenter la capaeit6 de certains

arcs (les aecroissements de capacit6 sont des fonctions

en escalier des investissements). Une l imite supdrieure

h la somme des invest issements effectuds 6taut don-

n6e, comment 6tendre le r6seau de fagon h c e que la

valeur du riot max imal de s h t soit maximale ?

Ce probl~me a 6t6 abord6 par de nombreux auteurs.

Par exemple, Fulkerson [19] dans le cas continu,

Christofides [20] clans le cas discret.

Lorsque le graphe G est planaire, on peut construire

le graphe dual G* et a t t r ibuer h chaque arc de G*

une longueur 6gale h la capaeit6 de Fare correspondant

darts G. Les coupes de G correspondent alors h des

chemins 616mentaires de G*; la coupe minimale de

G a un plus court chemin dans G*. Le probl~me de

l 'extension opt imale de G se t ransforme alors en un

problbme de plus court chemin darts G*, off la lon-

gueur de eertains arcs peut 6tre augment6e par des

invest issements ; par suite, et de fagon analogue h ce

qui a 6t6 f a r en VI-1, en un probl~me de plus court

there in avec contrainte .

11/12 A. TI~LEC., 30, n oB 11-12, 1975

394 M. MINOUX, -- PLUS COURT CHEMIN AVEC CONTRAINTES

VI-4 . P lus court s c h e m i n s dana lea graphes probabil istea.

Au lieu d 'associer h chaque arc u de G = [X, U] une longueur cer ta ine lu., on associe une var iable al~atoire ?(u de moyenne ixu et de var iance aZu eonnues.

On suppose que les ;(u (pour u ~ U) sont toutes inddpendanles. S i x ~ Q est un chemin jo ignan t s e t t dans G, on ddfinit sa longueur moyenne pa r :

ix(x) = Y~ ptu et sa var iance par a2(x) = Y~ a~u. u Gx u Ex

Une g6ndral isat ion in tdressante du probl~me du plus cour t chemin est alors de rechercher un chemin x ~ Q r6al isant un bon compromis entre la moyenne ix(x) et la var iance a(x). Pour cela, on recherchera (6ven- tue l lement pour plusieurs maleurs de a~, .) un chemin x tel que la moyenne Or(x) soit minimale , sous la

con t ra in te (~2(x)x< a~ma~"

Un problbme voisin est la recherche d 'un ordon- nancemen t darts un rdseau PERT (program eva lua t ion and review technique, t echnique de contr61e et d 'dva lua t ion des p rogrammes) s tochas t ique (oh chaque thche a une dur6e al6atoirc de moyenne et de var iance connues) : on se ram+ne de fa~on similaire au calcul d ' un chemin cr i t ique (plus long chemin) en moyenne avec une cont ra in te sur la var iance.

Manuscril refu le 16 ju in 1975.

BIBLIOGRAPt t IE

[If YE~ (J. Y.). Finding the lengths of all shortest paths in N mode non negative distance complete networks using 1/2 N a additions and N a comparisons (Recherche de tous les plus courts chemins dans un rdseau com- plet b. N nceuds en 1/2 _IV 3 additions et -IV 3 compa- raisons). J. ass. Computg. Machin., U. S. A. (juil. 1972), 19, n ~ 3, pp. 423-424.

[2] GRASSIN (J . ) , MINOUX (M.). Variation sur un algo- rithme de Dantzig; application h la recherche des plus courts chemins dans les grands rdseaux. Bey. ]r. Automat., In]ormat. Rech. operat. (mars 1973), 7, no l , pp. 53-62.

[3] DREYFUS (S. E.). An appraisal of some shortest path algorithms (Evaluation de quelques algorithmes de plus court chemin). Operat. Res., U. S. A. (1969), 17, n ~ 3, pp. 395-412.

[4] DIJKSTnA (E. W.). A note on two problems in con- nexion with graphs (Note sur deux probl+mes de la th~orie des graphes). Numer. Math., Dtsch. (1959), 1, n ~ 5, pp. 269-271.

[5] JOCKSCH (H. C.). The shortest route problem with constraints (Probl+me du plus court chemin avec

contraintes). J. Math. Anal. Appl., U . S . A . (1966), 14, pp. 191-197.

[6] BELLMAN (R.). Dynamic programming (Programma- tion dynamique). Princeton University Press, New York (1957), 342 p.

[7] :BELLMAN (R.). On a routing problem (Sur un pro- bl6me de routage). Quart. Appl. Math., U .S .A . (1958), 16, pp. 87-90.

[8] BERGE (C.). Thdorie des graphes et ses applications. Dunod, Paris (1958), 278 p.

[9] SHAPIRO (J. F.), FISCHER (M. L.). Constructive duality in integer programming (Dualitd constructive en programmation enti6re). S I A M J. Appl. Math., U . S . A . (jnil. 1974), 27, n ~ 1, pp. 31-52.

[ I 0 ] GRINOLD (R. C.). Steepest ascent for large scale linear programs (Mdthodes de plus forte pente pour les grands programmes lindaires). S.I.A.M. Bey., U . S . A . (juil. 1972), 14, n ~ 3, pp. 447-464.

[11] HELD (H.), WOLFE (P.), CROWDER (H. P.). Validation of subgradient optimization (Validation des m~thodes d'optimalisation par sous-gradients). Math. Pro- gramming, Netherl. (fdv. 1974), 6, n ~ I, pp. 62-88.

[12] LEGENDRE (J. P.), MINocx (M.). Dualit6 en pro- grammation enti6re et probl6mes de sdlection et d'affectation optimales de flotte. Rev. fr. Automat. Inform. rech. operat., Revue verte. (A paraltre.)

[13] GLOVEn (F.). Surrogate constraints (Contraintes suppl6mentaires). Operat. Res., U . S . A . (juil.-aoflt 1968), 16, n ~ 4, pp. %1-749.

[14] SHAHaO (J. F.). Generalized Lagrange multipliers in integer programming (Multiplicateurs de Lagrange g6ndralisds en programmation en nombres entiers). Operat. Res., U . S . A . (jan-fev. 1971), 19, n ~ l , pp. 68-76.

[15] M~Noux (M.). Structures algdbriques gdn6ralisdes des probl~mes de cheminement dans les graphes : thdo- r~mes, algorithmes et applications. Rev. fr. Automat., Inform. Rech. Operat., Revue verte (juin 1976), 10, V-2.

[16] Hu (T. C.).Revised matrix algorithms for shortest paths (Algorithmes matriciels pour le calcul des plus courts chemins). S I A M J. Appl. Math., U. S. A. (jan. t967), 15, n ~ 1, pp. 207-218.

[17] GONDaAN (M.). Alg~bre lin6aire et cheminement dans un graphe. Rev. ft. Automat., Informat. Reeh. operat. (jan. 1975), 9, v-l , pp. 77-99.

[18] KAUFMANN (A.), DESnAZHLLE (G.). La mdthode du chemin critique. Dunod, Paris (1964), 170 p.

[19] FULKgnSON (D. R.). Increasing the capacity of a network : the parametric budget problem (Augmen- tation de la capacit6 d'un rdseau : le probl~me para- mdtrique h contrainte budg~taire). Management Science, U . S . A . (1959), 5, n ~ 4, pp. 472-483.

[20] CnnISTOFmES (N.), BnOOKEn (P.). Optimal expan- sion of an existing network (Extension optimale d'un r6seau existant). Mathematical Programming, Netherl. (avr. t974), 6, n ~ 2, pp. 197-211.

[21] Hu (T. C.). Integer programming and network flows (Programmation en nombres entiers et riots dans les graphes). Addison Wesley, Reading Mass. (1969), 452 p.

[22] FOnD (L. R.), FULKEnSON (D. R.). Flows in networks (Flots dans les graphes). Princeton University Press, New York (1962), 194 p.

A. TI~LEC., 30, n ~ 11o12, 1975 12/12