<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% !TeX TS-program = lualatex
% !TeX encoding = UTF-8
% Ceci est la documentation du package "dijkstra"
%
\documentclass[french,a4paper,10pt]{article}
\usepackage[margin=1cm]{geometry}
\usepackage[bottom]{footmisc}
\usepackage{libertine,boites,tikz,enumitem,babel,xspace,listings,dijkstra}
\usetikzlibrary{arrows.meta}
\usepackage[scaled=0.8]{GoMono}
\frenchbsetup{og=Â«,fg=Â»}
\def\DIJK{\texttt{\dijkname}\xspace}
\makeatletter
\def\code{\expandafter\code@i\string}
\def\code@i#1{%
	\begingroup
		\par\nobreak\medskip\parindent0pt
		\leftskip.1\linewidth
		\catcode`\^^I 13 \begingroup\lccode`\~`\^^I \lowercase{\endgroup\def~{\leavevmode\space\space\space\space}}%
		\let\do\@makeother \dospecials
		\ttfamily\small\@noligs
		\make@car@active\,{\string,{}}%
		\obeylines\obeyspaces
		\def\code@ii##1#1{##1\par\medbreak\endgroup}%
		\code@ii
}
\long\def\grab@toks#1\relax{\gdef\right@content{#1}}

\newcommand\disable@lig[1]{%
	\catcode`#1\active
	\begingroup
		\lccode`\~`#1\relax
		\lowercase{\endgroup\def~{\leavevmode\kern\z@\string#1}}%
}

\newcommand\make@car@active[1]{%
	\catcode`#1\active
	\begingroup
		\lccode`\~`#1\relax
		\lowercase{\endgroup\def~}%
}

\newcommand\exemple{%
	\begingroup
	\parskip\z@
	\exemple@}

\newcommand\exemple@{%
	\medbreak\noindent
	\begingroup
		\let\do\@makeother\dospecials
		\make@car@active\ { {}}%
		\make@car@active\^^M{\par\leavevmode}%
		\make@car@active\^^I{\space\space}%
		\make@car@active\,{\leavevmode\kern\z@\string,}%
		\make@car@active\-{\leavevmode\kern\z@\string-}%
		\make@car@active\&gt;{\leavevmode\kern\z@\string&gt;}%
		\make@car@active\&lt;{\leavevmode\kern\z@\string&lt;}%
		\@makeother\;\@makeother\!\@makeother\?\@makeother\:% neutralise frenchb
		\exemple@@
}

\newcommand\exemple@@[2][30]{%
	\xdef\@hparta{0.#1\linewidth}\xdef\@hpartb{0.\number\numexpr95-#1\relax\linewidth}%
	\def\@tempa##1#2{\exemple@@@{##1}}%
	\@tempa
}

\newcommand\exemple@@@[1]{%
	\xdef\the@code{#1}%
	\endgroup
		\begingroup
			\fboxrule0.4pt \fboxsep=5pt
			\let\breakboxparindent\z@
			\def\bkvz@top{\hrule\@height\fboxrule}%
			\def\bkvz@bottom{\hrule\@height\fboxrule}%
			\let\bkvz@before@breakbox\relax
			\def\bkvz@set@linewidth{\advance\linewidth\dimexpr-2\fboxrule-2\fboxsep\relax}%
			\def\bkvz@left{\vrule\@width\fboxrule\kern\fboxsep}%
			\def\bkvz@right{\kern\fboxsep\vrule\@width\fboxrule}%
			\breakbox
				\kern.5ex\relax
				\leavevmode$\vcenter{\hsize=\@hparta\relax
					\ttfamily\small\the@code\par}$%
				\hfill\vrule\hfill
				$\vcenter{\hsize=\@hpartb\relax
					\newlinechar`\^^M\everyeof{\noexpand}\scantokens{#1}\par}$%
			\endbreakbox
		\endgroup
	\medbreak
	\endgroup
}
\begingroup
	\catcode`\&lt;13 \catcode`\&gt;13
	\gdef\verb{\relax\ifmmode\hbox\else\leavevmode\null\fi
		\bgroup
			\verb@eol@error \let\do\@makeother \dospecials
			\verbatim@font\@noligs
			\catcode`\&lt;13 \catcode`\&gt;13 \def&lt;{\begingroup$\langle$\itshape}\def&gt;{$\rangle$\endgroup}%
			\@ifstar\@sverb\@verb}
\endgroup
\def\longfrdijkdate@i#1/#2/#3\@nil{\number#3\relax\space \ifcase#2 \or janvier\or fÃ©vrier\or mars\or avril\or mai\or juin\or juillet\or aout\or septembre\or octobre\or novembre\or dÃ©cembre\fi\space#1}
\edef\longfrdijkdate{\expandafter\longfrdijkdate@i\dijkdate\@nil}
\makeatother
\begingroup
	\catcode`\_11 
	\gdef\cleval#1#2{%
		\bigbreak\noindent
		\hbox to .25\linewidth{%
			\color{teal}\bfseries\ttfamily
			\detokenize{#1}=$\langle$\detokenize{#2}$\rangle$\hss}\kern2.5em 
		(\textit{DÃ©faut} : {\color{teal}\ttfamily
		\skv_eearg\skv_ifempty{\useKV[\dijkname]{#1}}
			{$\langle$vide$\rangle$}
			{"\detokenize\expandafter\expandafter\expandafter{\useKV[\dijkname]{#1}}"}})%
		\par\nobreak
	}
\endgroup
\begin{document}
\parindent=0pt
\thispagestyle{empty}
\begin{titlepage}
	\begingroup
		\centering
		\null\vskip.25\vsize
		{\large\bfseries L'extension pour \LaTeX\par \Huge \dijkname\par}%
		\bigbreak
		v \dijkver
		\smallbreak
		\longfrdijkdate
		\vskip1.5cm
		Christian \bsc{Tellechea}\par
		\texttt{unbonpetit@netc.fr}\par
	\endgroup
	\vskip2cm
	\leftskip=.2\linewidth \rightskip=.2\linewidth \small
	Cette petite extension met en \oe uvre l'algorithme de Dijkstra pour des graphes pondÃ©rÃ©s, orientÃ©s ou non : le tableau de recherche du plus court chemin peut Ãªtre affichÃ©, la distance minimale entre deux sommets et le chemin correspondant sont stockÃ©s dans des macros.
\end{titlepage}
\parindent0pt

\section{Un exemple}
Dans le graphe \emph{non orientÃ©} suivant, quel est le plus court chemin pour aller de A Ã&nbsp; F ?

\begin{center}
	\begin{tikzpicture}[scale=1.75]
	\begin{scope}[every node/.style={inner sep=1pt,outer sep=0pt,circle,draw}]
	\node(A) at(0,0) {A}
	node(B) at(1,1) {B}
	node(C) at(3,1) {C}
	node(D) at(1,-1) {D}
	node(E) at(3,-1) {E}
	node(F) at(4,0) {F};
	\end{scope}
	\begin{scope}[every node/.style={inner sep=0pt,outer sep=2pt,midway,sloped,above}]
	\footnotesize\bfseries
	\draw(A)--(B) node{7}
	(B)--(C) node{12}
	(C)--(D) node[pos=0.35]{5}
	(A)--(D) node{15}
	(D)--(E) node{2}
	(E)--(F) node{14}
	(B)--(E) node[pos=0.65]{4}
	(C)--(F) node{3}
	(B)--(F) node[pos=.65]{16};
	\end{scope}
	\end{tikzpicture}
\end{center}

\paragraph{Lire le graphe}
Pour trouver le plus court chemin pour aller de A Ã&nbsp; F, il faut d'abord lire le graphe. Comme il est frÃ©quent que les graphes soient peu peuplÃ©s, j'ai pris le parti de dÃ©finir un graphe par une liste d'adjacence. Ainsi, la macro \verb|\readgraph|, qui va lire le graphe, admet comme argument obligatoire une liste d'adjacence :

\code/\readgraph{
		A [B=7, D=15],
		B [C=12, E=4, F=16],
		C [D=5, F=3],
		D [E=2],
		E [F=14]
}/

Les espaces sont ignorÃ©s de part et d'autre des noms des sommets, des crochets (ouvrants et fermants), des signes Â«\verb/=/Â» et des virgules. Ainsi, ce n'est que dans les noms des sommets que les espaces ne sont pas ignorÃ©s : par exemple, le sommet Â«\verb|A 1|Â» est distinct du sommet Â«\verb*|A1|Â».

\paragraph{Conditions sur les distances}
Les distances entre sommets \emph{doivent} Ãªtre positives, c'est une limitation intrinsÃ¨que Ã&nbsp; l'algorithme de Dijkstra pour qu'il fonctionne sans erreur. La mÃ©thode de programmation utilisÃ©e dans cette extension exige de plus que ces distances soient des nombres \emph{entiers}.\medbreak
Une fois que le graphe a Ã©tÃ© lu, celui-ci est rendu \emph{non orientÃ©} en interne et donc en coulisses, la liste d'adjacence devient

\code/A [B=7, D=15],
B [A=7, C=12, E=4, F=16],
C [B=12, D=5, E=3],
D [A=15, C=5, E=2],
E [D=2, B=4, F=14],
F [B=16, C=3, E=14]/

Par consÃ©quent, la liste d'adjacence entrÃ©e par l'utilisateur ne doit pas contenir d'incohÃ©rence. Si l'on spÃ©cifie la distance entre un sommet A et un sommet B par \verb|A[B=&lt;x&gt;,...]| on peut s'Ã©conomiser la peine de spÃ©cifier cette mÃªme distance entre B et A puisque c'est fait par l'extension \DIJK automatiquement. En revanche, une erreur sera Ã©mise si dans la liste d'adjacence, on trouve \verb|A[B=&lt;x&gt;,...]| puis \verb|B[A=&lt;y&gt;,...]| oÃ¹ \verb-&lt;y&gt;- et \verb-&lt;x&gt;- sont diffÃ©rents.

\paragraph{Lancer l'algorithme}
Une fois que le graphe est lu par la macro \verb|\readgraph|, on lance l'algorithme avec \verb|\dijkstra{&lt;A&gt;}{&lt;B&gt;}| oÃ¹ \verb-&lt;A&gt;- et \verb-&lt;B&gt;- sont deux sommets du graphe. La distance minimale entre ces deux sommets est stockÃ©e dans la macro \verb|\dijkdist| et le chemin correspondant dans \verb|\dijkpath|.

\exemple|\readgraph{
	A [B=7, D=15],
	B [C=12, E=4, F=16],
	C [D=5, F=3],
	D [E=2],
	E [F=14]}
Tableau : \dijkstra{A}{F}\par
Distance A-F = \dijkdist\par
Chemin = \dijkpath|

Dans le tableau, les colonnes sont disposÃ©es dans le \emph{mÃªme ordre} que celui des sommets dans la liste d'adjacence lue par \verb|\readgraph|.

\section{Graphe orientÃ©}
Pour spÃ©cifier Ã&nbsp; \verb|\readgraph| que la liste d'adjacence est celle d'un graphe \emph{orientÃ©}, la macro doit Ãªtre suivie d'une Ã©toile.

\begin{center}
	\begin{tikzpicture}[scale=1.75]
	\begin{scope}[every node/.style={inner sep=1pt,outer sep=0pt,circle,draw}]
	\node(A) at(0,0) {A}
	node(B) at(1,1) {B}
	node(C) at(1,0) {C}
	node(D) at(1,-1) {D}
	node(E) at(2,0) {E}
	node(F) at(3,1) {F}
	node(G) at(3,-1) {G}
	node(H) at(4,0) {H};
	\end{scope}
	\begin{scope}[-{Stealth[length=7pt,width=5pt,inset=3pt]},every node/.style={inner sep=0pt,outer sep=2pt,midway,sloped,above}]
		\footnotesize\bfseries
		\draw(A)--(B) node{5};
		\draw(A)--(C) node{3};
		\draw(A)--(D) node{2};
		\draw(C)--(B)node{1};
		\draw(D)--(C) node{1};
		\draw(B)--(F) node {2};
		\draw(B)--(E) node {2};
		\draw(D)--(E) node {3};
		\draw(D)--(G) node{2};
		\draw(F)--(E) node{4};
		\draw(E)--(G)node{4};
		\draw(G)--(F)node{1};
		\draw(G)--(H)node{8};
		\draw(F)--(H)node{5};
		
	\end{scope}
\end{tikzpicture}
\end{center}

Cela donne
\exemple|\readgraph*{
	A[B=5, C=3, D=2],
	B[E=2, F=2],
	C[B=1],
	D[C=1, E=3, G=2],
	E[G=4],
	F[E=4, H=5],
	G[F=1, H=8]}
Tableau : \dijkstra{A}{H}\par
Distance A-H = \dijkdist\par
Chemin = \dijkpath|

\section{ParamÃ¨tres}
\paragraph{ParamÃ¨tres de \texttt{\char`\\ dijkstra}}
Des \verb|&lt;paramÃ¨tres&gt;| peuvent Ãªtre passÃ©s Ã&nbsp; la macro \verb|\dijkstra| dans son argument optionnel qui prend la forme d'une liste de \verb|&lt;clÃ©&gt;=&lt;valeur&gt;|.

On peut Ã©galement rÃ©gler des \verb|&lt;paramÃ¨tres&gt;| pour toutes les exÃ©cutions de la macro \verb|\dijkstra| Ã&nbsp; venir avec
\begin{center}
	\verb|\setdijk{&lt;paramÃ¨tres&gt;}|
\end{center}
mais aussi modifier des \verb|&lt;paramÃ¨tres&gt;| \emph{par dÃ©faut} avec
\begin{center}
	\verb|\setdijkdefault{&lt;paramÃ¨tres&gt;}|
\end{center}

Pour rÃ©initialiser toutes les \verb|&lt;clÃ©s&gt;| Ã&nbsp; leur \verb|&lt;valeur&gt;| par dÃ©faut, il faut exÃ©cuter la macro \verb|\initdijk|.\medbreak

Voici toutes les \verb|&lt;clÃ©s&gt;|, leur \verb|&lt;valeur&gt;| par dÃ©faut et leur description.

\cleval{show-tab}{boolÃ©en}
Lorsque cette \verb|&lt;clÃ©&gt;| est \verb|true|, le tableau est affichÃ© par la macro \verb|\dijkstra|. Il ne l'est pas dans le cas contraire.

\cleval{v-position}{texte}
Ce paramÃ¨tre est placÃ© dans l'argument optionnel de \verb|\begin{tabular}[&lt;v-position&gt;]| pour spÃ©cifier la position que doit avoir le tableau par rapport Ã&nbsp; la ligne de base.

\cleval{pre-tab}{code}
Ce \verb|&lt;code&gt;| arbitraire est exÃ©cutÃ© juste avant le \verb|\begin{tabular}|.

\cleval{post-tab}{code}
Ce \verb|&lt;code&gt;| arbitraire est exÃ©cutÃ© juste aprÃ¨s le \verb|\end{tabular}|.

\cleval{col-type}{code}
Ce \verb|&lt;code&gt;| est le descripteur des colonnes contenant les sommets.

\cleval{infinity-code}{code}
Ce \verb|&lt;code&gt;| est exÃ©cutÃ© pour exprimer une distance infinie dans le tableau et dans la macro \verb|\dijkdist|.

\cleval{norevisit-code}{code}
Ce \verb|&lt;code&gt;| est exÃ©cutÃ© dans le tableau pour exprimer qu'un sommet a dÃ©jÃ&nbsp; Ã©tÃ© fixÃ©.

\cleval{h-rules}{boolÃ©en}
Lorsque ce boolÃ©en est \verb|true|, les rÃ©glures horizontales entre les Ã©tapes sont tracÃ©es dans le tableau.

\exemple|\readgraph{
	A [B=7, D=15],
	B [C=12, E=4, F=16],
	C [D=5, F=3],
	D [E=2],
	E [F=14]}
Tableau :
\dijkstra[h-rules=true,
          v-position=b]{A}{F}|

\cleval{show-lastcol}{boolÃ©en}
Lorsque ce boolÃ©en est \verb|true|, une colonne supplÃ©mentaire est affichÃ©e dans le tableau; cette colonne correspond au sommet fixÃ©.

\cleval{lastcol-type}{code}
Ce \verb|&lt;code&gt;| est le descripteur de la colonne correspondant au sommets fixÃ©s.

\cleval{lastcol-label}{code}
Ce \verb|&lt;code&gt;| contient le nom de la colonne correspondant aux sommets fixÃ©s.

\exemple|\readgraph{
	A [B=7, D=15],
	B [C=12, E=4, F=16],
	C [D=5, F=3],
	D [E=2],
	E [F=14]}
Tableau :
\dijkstra[show-lastcol]{A}{F}|

\cleval{nopath-string}{code}
Ce \verb|&lt;code&gt;| est placÃ© dans la macro \verb|\dijkpath| dans le cas oÃ¹ aucun chemin n'a pu Ãªtre trouvÃ©, comme cela peut Ãªtre le cas si le graphe est non connexe.

\exemple|\readgraph{
	A [B=2],
	B [C=3],
	D [E=5]}
\dijkstra[show-tab=false]{A}{E}
Chemin = \dijkpath\par
Distance A-E= \dijkdist|

\cleval{path-sep}{code}
Ce \verb|&lt;code&gt;| est insÃ©rÃ© entre chaque sommet dans la macro \verb|\dijkpath|.

\paragraph{Formatage distance/sommet}
Lorsqu'un sommet a un prÃ©dÃ©cesseur, la macro \verb|\formatnodewithprev| se charge d'afficher la distance et le sommet. Cette macro prend deux arguments (la \verb|&lt;distance&gt;| et le \verb|&lt;sommet&gt;|) et sa dÃ©finition par dÃ©faut est

\code|\newcommand*\formatnodewithprev[2]%
{% #1=distance, #2=nom du noeud de provenance
	$#1_{\mathrm{#2}}$%
}|

ce qui a pour effet de mettre le sommet de provenance en indice de la distance. On peut redÃ©finir cette macro pour choisir une autre mise en forme comme ci-dessous oÃ¹ le sommet est placÃ© entre parenthÃ¨ses.

\exemple|\renewcommand*\formatnodewithprev[2]%
{%
	#1 (#2)%
}
\readgraph{
	A [B=7, D=15],
	B [C=12, E=4, F=16],
	C [D=5, F=3],
	D [E=2],
	E [F=14]}
Tableau : \dijkstra{A}{F}|

\paragraph{Mise en Ã©vidence du sommet fixÃ©}
Le premier sommet fixÃ© est celui de dÃ©part et sa distance est toujours 0.

La macro \verb|\highlightfistnode| prend comme argument la distance (qui est 0) et le traite pour effectuer sa mise en forme. Sa dÃ©finition par dÃ©faut, qui compose cette distance en gras, est :

\code|\newcommand*\highlightfirstnode[1]{$\mathbf{#1}$}|

Les autres sommets, lorsqu'ils sont fixÃ©s, apparaissent dans le tableau avec leur distance et leur nom et sont traitÃ©s par la macro \verb|\highlightnode| qui rend deux arguments. Sa dÃ©finition permet une mise en forme similaire Ã&nbsp; ce que fait \verb|\formatnodewithprev|, sauf que la distance et le sommet sont en gras:

\code|\newcommand*\highlightnode[2]%
{% #1=distance, #2=nom du noeud de provenance
	$\mathbf{#1}_{\mathrm{\mathbf{#2}}}$%
}|

Pour obtenir d'autre effets, on peut redÃ©finir ces macros. L'exemple donnÃ© n'est pas rÃ©aliste tant les effets sont incohÃ©rents, c'est simplement un aperÃ§u de ce qu'il est possible de faire :

\exemple|\renewcommand*\highlightfirstnode[1]%
{%
	\fboxsep=1pt 
	\fbox{\color{blue}$\mathbf{#1}$}%
}%
\renewcommand*\highlightnode[2]%
{% #1=distance, 
 %  #2=nom du noeud de provenance
	\color{red}$#1_\mathrm{#2}$%
}
\readgraph{
	A [B=7, D=15],
	B [C=12, E=4, F=16],
	C [D=5, F=3],
	D [E=2],
	E [F=14]}
Tableau : \dijkstra{A}{F}|

\section{Code}
Le code ci-dessous est l'exact verbatim du fichier \verb|dijkstra.sty| :

\lstinputlisting[
	language=TeX,
	moretexcs={unless,ifcsname,ifdefined,detokenize,numexpr,dimexpr,glueexpr,unexpanded},
	basicstyle=\small\ttfamily\color{black!25},
	identifierstyle=\bfseries\color{white},%
	backgroundcolor=\color{black!85},
	keywordstyle=\bfseries\color{orange},
	commentstyle=\color{cyan!66},
	columns=fixed,
	alsoletter={\_},
	tabsize=2,
	extendedchars=true,
	showspaces=false,
	showstringspaces=false,
	numbers=left,
	numberstyle=\tiny\ttfamily\color{black},
	breaklines=true,
	prebreak={\hbox{$\hookleftarrow$}},
	breakindent=3em,
	breakautoindent=true,
	xleftmargin=1em,
	xrightmargin=0pt,
	lineskip=0pt,
	numbersep=1em,
	classoffset=1,
	alsoletter={\_},
	morekeywords={dijkstra,dijkdist,dijkpath,initdijk,setdijk,setdijkdefault,formatnodewithprev,highlightnode,highlightfirstnode},
	keywordstyle=\bfseries\color{red!85!black},
	classoffset=0,
]{dijkstra.sty}
\end{document}</pre></body></html>