De même, pour trouver un plus court chemin allant de 1 à 5, on observe que
P
5
1,5 = 3, donc le chemin commence par 1, 3 ; les sommets suivants sont P
5
3,5 = 2,
puis P
5
2,5 = 5 ; il s’agit donc du chemin (1, 3, 2, 5) de poids D
5
1,5 = 4.
Algorithme de recherche d'un chemin de poids minimum
On numérote de 1 à n les sommets du graphe et l’on suppose que pour chaque arc
i, j , on a défini un poids d i,j pour le chemin (i, j) et un poids d j,i pour le chemin
(j, i). S’il n’y a pas d’arc entre les sommets i et j , on définit ces nombres en leur
donnant une valeur très grande par rapport aux poids.
Étape 1. On construit les tableaux D et P à n lignes et n colonnes en posant D i,j =
d i,j et P i,j =j pour 1in et 1jn (i est l’indice de la ligne, j celui de la colonne).
Étape 2. Pour k de 1 à n, exécuter la tâche suivante :
pour i de 1 à n, pour j de 1 à n,
si D i,k + D k,j < D i,j , alors
D i,j ← D i,k + D k,j et P i,j ← P i,k
.
Après exécution de cet algorithme, D i,j est le poids minimum d’un chemin de i vers
j . Les sommets successifs d’un tel chemin sont i, i 1 = P i,j , i 2 = P i 1 ,j , etc. Mis à part
le point de départ i, ces sommets se lisent en parcourant dans un ordre convenable
la j -ième colonne de P .
3.3 Le problème du flot maximum
Exemple.
a
b
c
d
t
s
(1)
(1)
(2)
(3)
(3)
(4)
(4)
(4)
(5)
figure 1
À partir d’une station de pompage située en s, un réseau de conduites permet d’acheminer du pétrole en des lieux a, b, c, d et t. Ci-dessous le plan du réseau.
La flèche indique le sens d’écoulement dans chaque conduite et le chiffre entre
parenthèses indique la capacité de la conduite,
c’est-à-dire le débit maximum, en barils par heure.
On obtient un graphe dont les arcs représentent
les conduites. Mais chaque arc possède une origine et une extrémité, donc nous désignons les
arcs par des couples : (s, a), (s, c), (c, a), (a, b),
(c, d), (c, b), (b, d), (b, t) et (d, t).
Le graphe est dit orienté.
On veut faire transiter de s à t le plus de pétrole possible en réglant convenablement
le débit dans chaque conduite. Un régime d’écoulement est déterminé par
® le débit F assuré par la station de pompage s,
® la capacité de chaque conduite (u, v)
® la quantité de pétrole f (u, v) qui transite en une heure dans la conduite (u, v).
La quantité pompée en s étant d’abord envoyée vers a et c, on a
f (s, a) + f (s, c) = F
86 – GRAPHES
P
5
1,5 = 3, donc le chemin commence par 1, 3 ; les sommets suivants sont P
5
3,5 = 2,
puis P
5
2,5 = 5 ; il s’agit donc du chemin (1, 3, 2, 5) de poids D
5
1,5 = 4.
Algorithme de recherche d'un chemin de poids minimum
On numérote de 1 à n les sommets du graphe et l’on suppose que pour chaque arc
i, j , on a défini un poids d i,j pour le chemin (i, j) et un poids d j,i pour le chemin
(j, i). S’il n’y a pas d’arc entre les sommets i et j , on définit ces nombres en leur
donnant une valeur très grande par rapport aux poids.
Étape 1. On construit les tableaux D et P à n lignes et n colonnes en posant D i,j =
d i,j et P i,j =j pour 1in et 1jn (i est l’indice de la ligne, j celui de la colonne).
Étape 2. Pour k de 1 à n, exécuter la tâche suivante :
pour i de 1 à n, pour j de 1 à n,
si D i,k + D k,j < D i,j , alors
D i,j ← D i,k + D k,j et P i,j ← P i,k
.
Après exécution de cet algorithme, D i,j est le poids minimum d’un chemin de i vers
j . Les sommets successifs d’un tel chemin sont i, i 1 = P i,j , i 2 = P i 1 ,j , etc. Mis à part
le point de départ i, ces sommets se lisent en parcourant dans un ordre convenable
la j -ième colonne de P .
3.3 Le problème du flot maximum
Exemple.
a
b
c
d
t
s
(1)
(1)
(2)
(3)
(3)
(4)
(4)
(4)
(5)
figure 1
À partir d’une station de pompage située en s, un réseau de conduites permet d’acheminer du pétrole en des lieux a, b, c, d et t. Ci-dessous le plan du réseau.
La flèche indique le sens d’écoulement dans chaque conduite et le chiffre entre
parenthèses indique la capacité de la conduite,
c’est-à-dire le débit maximum, en barils par heure.
On obtient un graphe dont les arcs représentent
les conduites. Mais chaque arc possède une origine et une extrémité, donc nous désignons les
arcs par des couples : (s, a), (s, c), (c, a), (a, b),
(c, d), (c, b), (b, d), (b, t) et (d, t).
Le graphe est dit orienté.
On veut faire transiter de s à t le plus de pétrole possible en réglant convenablement
le débit dans chaque conduite. Un régime d’écoulement est déterminé par
® le débit F assuré par la station de pompage s,
® la capacité de chaque conduite (u, v)
® la quantité de pétrole f (u, v) qui transite en une heure dans la conduite (u, v).
La quantité pompée en s étant d’abord envoyée vers a et c, on a
f (s, a) + f (s, c) = F
86 – GRAPHES