blob: d261c6f84bf41321c9edda435aacd6e1aef32321 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
\section{Dijkstra}
{\large Algorithme de Dijkstra :} Plus courte chaîne du sommet $E$ au sommet $S$.
\medskip
\subsection{Dijkstra exemple 1}
\medskip
\begin{center}
\begin{tkzexample}[vbox]
\begin{tikzpicture}
\GraphInit[vstyle=Dijkstra]
\SetGraphUnit{4}
\Vertices{square}{B,C,D,A}
\SetGraphUnit{2.82}
\NOWE(B){E}
\NOEA(C){S}
\Edge[label=$3$](E)(A)
\Edge[label=$1$](E)(B)
\Edge[label=$1$](A)(B)
\Edge[label=$3$](B)(C)
\Edge[label=$3$,style={pos=.25}](A)(C)
\Edge[label=$5$,style={pos=.75}](B)(D)
\Edge[label=$4$](A)(D)
\Edge[label=$1$](S)(D)
\Edge[label=$3$](C)(S)
\Edge[label=$1$](C)(D)
\end{tikzpicture}
\end{tkzexample}
\end{center}
\def\ry{$\vrule width 5pt$}
\def\iy{$\infty$}
%<–––––––––––––––––——————————————————————————————————————————————————————————>
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hskip\tabskip\hrule}}
\halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&& $E$ && $A$ && $B$ && $C$ && $D$ && $S$ && Choix &\cr\tablerule
&& $0$ && \iy && \iy && \iy && \iy && \iy && $E$ &\cr\tablerule
&& \ry && $3(E)$ && $1(E)$ && \iy && \iy && \iy && $B$ &\cr\tablerule
&& \ry && $2(B)$ && \ry && $4(B)$ && $6(B)$ && \iy && $A$ &\cr\tablerule
&& \ry && \ry && \ry && $4(B)$ && $6(B)$ && \iy && $C$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && $5(C)$ && $7(C)$ && $D$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && $6(D)$ && $S$ &\cr\tablerule}}
%<–––––––––––––––––——————————————————————————————————————————————————————————>
\medskip
Le plus court chemin est donc $EBCDS$
\vfill\newpage
\subsection{Dijkstra exemple 2}
\medskip
\begin{center}
\begin{tkzexample}[vbox]
\begin{tikzpicture}
\GraphInit[vstyle=Dijkstra]
\SetGraphUnit{4}
\Vertices{square}{G,D,A,F}
\WE(F){H}
\EA(A){B}
\EA(D){C}
\NO(A){E}
\Edge[label=$1$](H)(F)
\Edge[label=$4$](G)(F)
\Edge[label=$2$](H)(G)
\Edge[label=$2$](G)(D)
\Edge[label=$3$](D)(C)
\Edge[label=$4$](F)(E)
\Edge[label=$3$](A)(D)
\Edge[label=$2$](A)(E)
\Edge[label=$1$](A)(B)
\Edge[label=$2$](A)(C)
\Edge[label=$2$](C)(B)
\Edge[label=$3$](E)(B)
\end{tikzpicture}
\end{tkzexample}
\end{center}
%<–––––––––––––––––——————————————————————————————————————————————————————————>
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hskip\tabskip\hrule}}
\halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&& $H$ && $F$ && $G$ && $E$ && $D$ && $A$ && $C$ && $B$ && Choix &\cr\tablerule
&& $0$ && \iy && \iy && \iy && \iy && \iy && \iy && \iy && $H$ &\cr\tablerule
&& \ry && $1(H)$ && $2(H)$ && \iy && \iy && \iy && \iy && \iy && $F$ &\cr\tablerule
&& \ry && \ry && $2(H)$ && $5(F)$ && \iy && \iy && \iy && \iy && $G$ &\cr\tablerule
&& \ry && \ry && \ry && $5(F)$ && $4(G)$ && \iy && \iy && \iy && $D$ &\cr\tablerule
&& \ry && \ry && \ry && $5(F)$ && \ry && $7(D)$ && $7(D)$ && \iy && $E$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && $7(D)$ && $7(D)$ && $8(E)$ && $A$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $8(E)$ && $C$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && \ry && \ry && $8(E)$ && $B$ &\cr\tablerule}}
%<–––––––––––––––––——————————————————————————————————————————————————————————>
Le plus court chemin est donc $HFEB$
\begin{tkzexample}[code only]
\def\ry{$\vrule width 5pt$}
\def\iy{$\infty$}
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hskip\tabskip\hrule}}
\halign to \hsize{\strut#&\vrule # \tabskip=0.6em plus8em&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#&
\hfil#\hfil& \vrule#\tabskip=0pt\cr\tablerule
&& $H$ && $F$ && $G$ && $E$ && $D$ && $A$ && $C$ && $B$%
&& Choix &\cr\tablerule
&& $0$ && \iy && \iy && \iy && \iy && \iy && \iy && \iy%
&& $H$ &\cr\tablerule
&& \ry && $1(H)$ && $2(H)$ && \iy && \iy && \iy && \iy && \iy%
&& $F$ &\cr\tablerule
&& \ry && \ry && $2(H)$ && $5(F)$ && \iy && \iy && \iy && \iy%
&& $G$ &\cr\tablerule
&& \ry && \ry && \ry && $5(F)$ && $4(G)$ && \iy && \iy && \iy%
&& $D$ &\cr\tablerule
&& \ry && \ry && \ry && $5(F)$ && \ry && $7(D)$ && $7(D)$ && \iy%
&& $E$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && $7(D)$ && $7(D)$ && $8(E)$%
&& $A$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && \ry && $7(D)$ && $8(E)$%
&& $C$ &\cr\tablerule
&& \ry && \ry && \ry && \ry && \ry && \ry && \ry && $8(E)$%
&& $B$ &\cr\tablerule}}
\end{tkzexample}
\endinput
|