La lecture à portée de main
7
pages
Français
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
7
pages
Français
Ebook
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
T ES
...........................
...............
...............
.......................................
trouv
er.
Comme
a
de
ts
nous
parmi
en
don
a
livreur
v
ar?tes
ons
plus
l'habitude,
passan
il
est
oser
ais?
un
de
est
remarquer
que
une
de
p
telles
?
situations
ts
p
son
euv
ositifs.
en
el?s
t
parcours
se
.
ramener
esoin
?
nom
l'?tude
p
d'un
osen
graphe.
tre
Les
qui
math?maticiens
Dans
et
informaticiens
I)
on
de
t
4
prop
os?
un
div
les
erses
aect?es
m?tho
ts
des
(ou
t
algorithmes)
ses
p
doit
our
pizzas,
r?soudre
hemin.
le
probl?me
trouv
du
ons
plus
situations
somme
hemin.
ts
Une
la
des
Une
solutions
haine
les
sommets
plus
relien
est
ha?ne
un
algorithme
he
qui
?s
p
aphes
orte
(partie
le
?
nom
graphes
de
de
son
Sp
in
en
v
la
en
est
teur,
graphe
l'informaticien
t
n?erlandais
ar?tes
Edsger
t
Dijkstra
de
et
a
p
?t?
Ces
publi?
en
son
1959.
app
Mais
a
?
v
prop
an
que
?
aux
solution
de
Exemple
Du
V
un
Le
p
plus
A
er
E
de
B
b
3
v
1
nous
5
breuses
1
d'une
3
haine
de
la
nouv
des
elles
oin
notions.
des
1.1
qui
D?nitions
D?nition
t.
1
plus
Gr
aphe
en
p
deux
ond?r
est,
?
les
Un
ha?nes
dit
les
probl?me
t,
dit
qui
de
Et
hemin
ts.
fr?quen
d'un
plus
herc
des
1
est
ond?r
probl?me
orient?s,
Gr
ternet,
I
in
graphes
sur
l'aide
donn?es
probl?mes
des
R?solution
mission
l'aide
trans-
probl?mes
la
R?solution
par
?cialit?
t
t
Cours
d'?tudier
1
algorithme
nous
graphe
a
ond?r?.
v
C
ons
S
b
D
esoin,
3
1
toujours,
3
de
1
d?nir
1E S
1 ◦
◦
∞
2 ◦ X
◦ X
3 ◦ Y X p
X X Y
◦ p Y
p Y ◦
Y
4 ◦
◦
5
E A B C D S
∞ ∞ ∞ ∞ ∞ E
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
sous
vide
P
Sommet
allons
l'on
our
d'un
l'algorithme
haque
es
sommet
Sommet
?
de
t
plus
?
jusqu'au
la
:
,
le
?crire
la
sommets
somme
de
er
derni?re
en
0
tre
graphe
le
et
V
t
our
de
?rer
y
sous
et
de
du
t
p
2?me
oids
dans
de
Sommet
l'ar?te
Etap
relian
fur
t
les
ra
des
?
ligne
et
tableau,
.
ligne
les
Si
le
elle
Dijkstra
est
vien
de
t
de
inf?rieur
les
au
es
le
la
t
sommets.
de
0
nouv
dans
et
la
le
ligne
0
pr?c?den
te,
du
inscrire
Sur
une
1?re
dans
graphe
la
tous
0
o
de
dan
?
te
hoisir
de
que
la
form?e
et
Commenecr
l'ensem
.
minimal.
Sommet
Sinon,
t
inscrire
utiliserons
le
utilisation
t.
et
t
en
de
hemin
t
trouv
de
allons
la
Algorithme
ligne
pro
pr?c?den
t,
te,
ainsi
suite
sommet
.
d?part.
ligne
par
?tap
des
p
remplir
ts
tableau
de
1.
la
dans
ligne
Rep
pr?c?den
autres
te.
de
les
sommet
t
S'il
reste
2.
des
d?part
sommets
sommet
non
sous
retourner
0
?
l'?tap
le
e
tableau,
2.
ligne
le
la
Sinon,
tableau.
passer
ligne
?
la
l'?tap
3.
e
du
5.
les
ligne
Placer
La
longueur
eectuer
minimale
he
est
e
le
l'algorithme.
nom
l'?x?cution
bre
mesure
lu
et
sur
au
la
derni?re
nous
ligne
sommets
du
par
tableau.
La
la
sommets
haine
ble
de
4.
longueur
os?e
minimale
est
se
premi?re
trouv
e
la
en
don
lisan
une
t
nous
le
de
tableau
haque
en
A
repartan
pr?c?den
t
du
du
sommets
dernier
tre
de
sommet
le
et
en
er
regardan
t
t
de
Nous
quel
de
sommet
et
1.2
la
2E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) D
E A B C D S
∞ ∞ ∞ ∞ ∞ E
3(E) 1(E) ∞ ∞ ∞ B
2(B) 4(B) 6(B) ∞ A
4(B) 6(B) ∞ C
5(C) 7(C) C
6(D) S
E−B−C−D−S
S
D D
C
v2
v v1 4
v3
..................
la
mani?re
suiv
orien
ar?tes
que
an
Sommet
te
que
:
an
dans
est
la
graphe
t?es,
gauc
eut
de
sens.
3
,
on
rep
l'origine
?re
plus
le
Sommet
p
t
oin
t
t
?
inscrit
ne
le
les
plus
un
en
2
bas,
en
:
?
Une
.
une
Puis
don
dans
l'extr?mit?
la
0
droite
0
on
un
note
don
le
les
sommet
son
inscrit
orien
le
plus
dire
en
l'on
bas,
p
de
parcourir
ar?tes
Le
dans
p
seul
oids
Exemple
de
t
l'?criv
3
he,
ha?ne
est
D?nition
6.
Boucle
2
b
Graphes
est
orien
ar?te
t?s
t?e
D?nition
t
2
et
Gr
donc
aphe
haine
orient?
Un
Une
graphe
orien
6.
t?
est
.
5.
On
l'obtien
Exemple
t
3A
B C
n
n n×n i
j i j 0
1 0 1A
A= 0 1 1
0 0 0
C
B
t
n
um?rot?s
une
Un
L
1
?tiquet?
?
p
?
est
?tiquet?s
une
les
matrice
bres
de
v
dimension
ts
tation
asso
aphe
matrice
orien
,
aect?es
o?
son
le
5
terme
:
guran
A
t
pas
en
des
ligne
mais
La
reli?s
et
t
3
orient?
5
est
Un
?gale
un
?
don
1
son
s'il
Remarque
existe
les
une
des
ar?te
ositifs.
d'orgine
graphes
aphe
t
et
ALEZY,
d'extr?mit?b
gr
E
,
non
et
a
un
ec
sinon.
sommets
Exemple
ts,
4
?
et
son
par
p
ar?te
sommets
oss?dan
les
l'orien
t
e
Graphes
D?nition
asso
Gr
e
?tiquet?
Matric
graphe
don
est
un
graphe
d'ordre
t?
t?
t
orien
ar?tes
p
t
est
d'?tiquettes.
graphe
2
dans
graphe
graphe
ond?r?
4
un
D?nition
?tiquet?
g?n?rer
lequel
de
?tiquettes
des
t
des.
nom
graphe
p
an
Exemple
p
Les
par
?tiquet?s
de
ermetten
les
de