/
exemple-dijkstra.tex
117 lines (93 loc) · 4.46 KB
/
exemple-dijkstra.tex
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
\begin{frame}{Exemple}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $s$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &2 &7 &6 &5 &3 &4 &t \\
\hline
\texttt{pred} & &s &s &s & & & & \\
\texttt{dist} & 0 &9 &15 &14 &$+\infty$ &$+\infty$ &$+\infty$ &$+\infty$ \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $2$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &7 &6 &5 &3 &4 &t \\
\hline
\texttt{pred} & &s &s &s & &2 & & \\
\texttt{dist} & 0 &9 &15 &14 &$+\infty$ &33 &$+\infty$ &$+\infty$ \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $6$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &7 &\textbf{6} &5 &3 &4 &t \\
\hline
\texttt{pred} & &s &s &s &6 &6 & & \\
\texttt{dist} & 0 &9 &15 &14 &44 &32 &$+\infty$ &$+\infty$ \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $7$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &\textbf{7} &\textbf{6} &5 &3 &4 &t \\
\hline
\texttt{pred} & &s &s &s &7 &6 & &7 \\
\texttt{dist} & 0 &9 &15 &14 &35 &32 &$+\infty$ &59 \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $3$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &\textbf{7} &\textbf{6} &5 &\textbf{3} &4 &t \\
\hline
\texttt{pred} & &s &s &s &3 &6 & &3 \\
\texttt{dist} & 0 &9 &15 &14 &34 &32 &$+\infty$ &51 \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $5$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &\textbf{7} &\textbf{6} &\textbf{5} &\textbf{3} &4 &t \\
\hline
\texttt{pred} & &s &s &s &3 &6 &5 &5 \\
\texttt{dist} & 0 &9 &15 &14 &34 &32 &45 &50 \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Itérations de l'algorithme : traitement de $4$}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &\textbf{7} &\textbf{6} &\textbf{5} &\textbf{3} &\textbf{4} &t \\
\hline
\texttt{pred} & &s &s &s &3 &6 &5 &5 \\
\texttt{dist} & 0 &9 &15 &14 &34 &32 &45 &50 \\
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Fin de l'algorithme}
\begin{center}
\includegraphics[height=.6\textheight]{fig/dijkstra-0.pdf}
\begin{tabular}{c|cccccccc}
& \textbf{s} &\textbf{2} &\textbf{7} &\textbf{6} &\textbf{5} &\textbf{3} &\textbf{4} &\textbf{t} \\
\hline
\texttt{pred} & &s &s &s &3 &6 &5 &5 \\
\texttt{dist} & 0 &9 &15 &14 &34 &32 &45 &50 \\
\end{tabular}
\end{center}
\end{frame}