diff options
Diffstat (limited to 'obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex')
-rw-r--r-- | obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex b/obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex new file mode 100644 index 0000000000..d261c6f84b --- /dev/null +++ b/obsolete/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex @@ -0,0 +1,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
\ No newline at end of file |