summaryrefslogtreecommitdiff
path: root/obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex
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