summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2021-01-22 03:00:46 +0000
committerNorbert Preining <norbert@preining.info>2021-01-22 03:00:46 +0000
commite1a7798f45cd37c0aa0bfaaef5f0acb4e48bc867 (patch)
treed2bbebcdb7bcb8fe013a9d3cbd2cff880b18afbf /macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex
parent37cb9bbabbfe1a8d0d1334832814ccbefcf9ac0a (diff)
CTAN sync 202101220300
Diffstat (limited to 'macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex')
-rw-r--r--macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex152
1 files changed, 152 insertions, 0 deletions
diff --git a/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex b/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex
new file mode 100644
index 0000000000..7f8b81d08b
--- /dev/null
+++ b/macros/latex/contrib/tkz/tkz-graph/doc/latex/TKZdoc-gr-Dijkstra.tex
@@ -0,0 +1,152 @@
+\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