path: root/Info/11/NTG/1/Dijkstra/slides.md

---
header-includes: |
    ```{=latex}
    \makeatletter
    \beamer@ignorenonframefalse
    \makeatother
    ```
    \usepackage{standalone}
    \usepackage{ulem}
    
    \usetikzlibrary{graphs, shapes, quotes}
    \usetikzlibrary{overlay-beamer-styles}
    
    \newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
    \usepackage{changepage}
    \newcommand\revealtexton[3]{\textbf{\only<-#2>{\textcolor{bg}{#1}}\only<#3->{\textcolor{red}{#1}}}}

    \newcommand\unkn{$\infty/-$}
    \newcommand\cur{\cellcolor{red!30}}
    \newcommand\done{\cellcolor{gray!30}}
---

## {.standout}
Herzlich Willkommen!

Du kannst dich schon anmelden

\texttt{v[orname].nachname}

und den Bildschirm ausschalten.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Warteschlange \hfill{} 1/3

### Diskutiert die Aussage {.t}

\vspace{0.2cm}

> Die Warteschlange der Breitensuche funktioniert genau wie ein Bücherstapel, der als \underline{letzte} eingefügte Knoten wird als \underline{Erstes} wieder betrachtet.

\begin{center}
\begin{tikzpicture}
\only<1>{
\node {\includegraphics[keepaspectratio, height=3cm]{img/Copyrighted/book-stack.png}};
}
\only<2>{
\draw[line width=2pt]
      (-1.3, -0.1) -- (1.3, -0.1)
      (-1.3, 1.1) -- (1.3, 1.1);
\node [
  fill=red!30, draw, 
  single arrow, minimum height=0.5cm,
  rotate=180, 
] at (-2, 0.5) {};
\node[fill=red!30, draw, circle, minimum width=1cm] at (-0.7, 0.5) {};
\node[] at (0, 0.5) {...};
\node[fill=blue!30, draw, circle, minimum width=1cm] at (0.7, 0.5) {};
\node [
  fill=blue!30, draw, 
  single arrow, minimum height=0.5cm,
  rotate=180, 
] at (2, 0.5) {};
}
\end{tikzpicture}
\end{center}

\pause

**Nein.** Die Warteschlange funktioniert genau wie an der Kasse, der \underline{erste} Knoten der eingefügt wird, wird auch als \underline{Erster} wieder betrachtet.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Knoten markieren \hfill{} 2/3

### Diskutiert die Aussage:

\vspace{0.2cm}

> Algorithmen, bei denen wir Knoten oder Räume farbig markieren, machen keinen Sinn!
> Sie sind für den Computer ungeeignet, da der Computer nichts farbig markieren kann.

\pause

\vspace{0.1cm}
**Quatsch!** Zwei Möglichkeiten:

::: {.columns}
:::: {.column width=60%}
* Attribut der Klasse `Knoten`
* Array, um die Markierungen zu speichern

\vspace{0.2cm}
\begin{center}
\begin{tikzpicture}
\begin{class}[]{Knoten}{0, 0}
\attribute{String bezeichnung}
\attribute{boolean markiert}
\operation{...}
\end{class}
\end{tikzpicture}
\end{center}
::::

:::: {.column width=45%}
\resizebox{\textwidth}{!}{
\begin{tikzpicture}
  \node at (-2.25, 4.5) {\textbf{Knotenfeld}};
  \node at (.5, 4.5) {\textbf{Markierungen}};

  \node[anchor=south west, minimum size=1cm, fill=gray!30] at (-3, 0) {};

  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {};
  }

  \foreach \y in {0,...,3} {
    \node at (-1.75, 3.5 - \y) {\textbf \y};
  }

  \begin{object}[text width=3cm]{v1: Knoten}{-5.15, 4.5}
    \attribute{name = "v1"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 3.5) {};
  \draw[-Triangle, thick] (-2.5, 3.5) -- (-3.5, 4);

  \begin{object}[text width=3cm]{v2: Knoten}{-5.15, 3}
    \attribute{name = "v2"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 2.5) {};
  \draw[-Triangle, thick] (-2.5, 2.5) -- (-3.5, 2.5);

  \begin{object}[text width=3cm]{v3: Knoten}{-5.15, 1.5}
    \attribute{name = "v3"}
  \end{object}
  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 1.5) {};
  \draw[-Triangle, thick] (-2.5, 1.5) -- (-3.5, 1);

  \node[] at (-5.8, -0.25) {\textbf{anzKnoten = 3}};

  \foreach \y in {0,...,3} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }

  \node[anchor=south west, minimum size=1cm, fill=gray!30] at (0, 0) {};
  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
  }

  \draw[Triangle-Triangle, thick, dashed] (-1.6, 3.5) -- (-0.4, 3.5);
  \node at (-1.75, 3.5) {\boldred{0}};
  \node at (-0.25, 3.5) {\textbf{\textcolor{magenta}{0}}};
\end{tikzpicture}
}
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Pfade \hfill{} 3/3

### Diskutiert die Aussage:

\vspace{0.2cm}

> Die Breitensuche findet in \underline{jedem} Graphen alle kürzesten Pfade, da die Entfernung der betrachteten Knoten immer um eine Kante pro Ebene zunimmt.

\pause

::: {.columns}
:::: {.column width=40%}
\only<5->{%
\vspace{0.3cm}
Nur in \boldred{ungewichteten} Graphen!

Kantenanzahl $\neq$ Pfadlänge
}
::::

:::: {.column width=40%}
\begin{tikzpicture}[
  graph vertex/.style={draw, circle, inner sep=3pt},
  edge label/.style={fill=bg},
  marked/.style={fill=blue!40},
  marked on/.style={alt=####1{marked}{}},
  active/.style={draw=red, fill=red!40},
  active on/.style={alt=####1{active}{}},
  bad/.style={draw=red, thick},
  bad on/.style={alt=####1{bad}{}},
  better/.style={draw=green!70!black, thick},
  better on/.style={alt=####1{better}{}},
]
  \node[graph vertex, marked on=<2->, active on=<2-3>] (1) {1};
  \node[graph vertex, marked on=<3->] (2) at (2, 0) {2};
  \node[graph vertex, marked on=<3->] (3) at (0, -2) {3};
  \node[graph vertex] (4) at (2, -2) {4};

  \graph[edge quotes mid] {
    (1) -> ["5" edge label, bad on=<4>] (2),
    (1) -> ["1" edge label, better on=<5>] (3),
    (3) -> ["1" edge label, better on=<5>] (4),
    (4) -> ["1" edge label, better on=<5>] (2),
  };
\end{tikzpicture}
::::
:::

## Hey Manfred!

::: {.columns align=center}
:::: {.column width=50%}
`\only<1>{`{=latex}
![](img/manfred_cut_out_sad_under_water.png)
`}\only<2>{`{=latex}
![](img/manfred_cut_out_sad.png)
`}\only<3->{`{=latex}
![](img/manfred_cut_out_autum.png)
`}`{=latex}
::::

:::: {.column width=50%}
`\only<1->{`{=latex}
Alle Rohre in Manfreds Labyrinth sind wieder repariert und das Wasser abgepumpt.
`\\[0.3cm]}\only<3->{`{=latex}
Jetzt kann der Herbst kommen.
Manfred verbringt die kürzer werdenden Tage gerne mit einer Kanne Tee in seinem Heimkino (Raum 13).
`}`{=latex}
::::
:::

## Manfred muss dringend Tee loswerden!

::: {.columns align=center}
:::: {.column width=50%}
Manfred hat zwei Toiletten in seinem Labyrinth:
\vspace{0.1cm}

* Das Badezimmer (Raum 2)
* Die Gästetoilette (Raum 14)

\vspace{0.1cm}

> Was ist der kürzeste Weg zu einer Toilette?
::::

:::: {.column width=50%}
\vspace{0.3cm}
![](img/manfreds_labyrinth_toilets.png)
::::
:::

##

\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, height=\textheight]{img/manfred_cut_out_autum.png}};
\only<-5>{
  \node[text width=7cm] at (7, 0) {Manfred hat Gott sei dank die Wege in seinem Labyrinth vermessen.};
}
\only<3-5>{
  \node[text width=7cm] at (7, -1.5) {Wie viele Möglichkeiten sind es, wenn Manfred einfach alle Wege ausprobiert?};
}
\only<4-5>{
  \node[text width=7cm] at (7, -2.5) {\boldred{257}};
}
\only<1>{
  \node[rotate=5, opacity=0] at (-1, -3) {\includegraphics[keepaspectratio, height=3cm]{img/Stoppuhr_digital_noBG_cutout.png}};
}
\only<2->{
  \node[rotate=5] at (-1, -3) {\includegraphics[keepaspectratio, height=3cm]{img/Stoppuhr_digital_noBG_cutout.png}};
}
\only<5->{
  \node at (7, 0) (ed) {\includegraphics[keepaspectratio, height=\textheight]{img/Edsger_Wybe_Dijkstra_cutout.png}};
  \node[below=0cm of ed] {Edsger Dijkstra \textcopyright{} Hamilton Richards};
}
\only<5>{
  \draw[line width=1.5pt]
    (6.75, -4) -- (10.5, -4)
    (5.5,-2.5) -- (8.5,-2.5)
    (6.5,-1.5) -- (10,-1.5)
    (7,0) -- (10,0)
    (6,2) -- (9, 2);
}
\only<6->{
  \node[scale=1.5] at (4, 2) {\Huge \faIcon[regular]{lightbulb}};
}
\end{tikzpicture}

## Erstmal klein anfangen

::: {.columns align=center}
:::: {.column width=50%}
![](img/manfreds_labyrinth_subgraph_toilets.png){height=5cm}
::::

:::: {.column width=50%}
\scalebox{1.2}{
\tikzstyle{start} = [fill=red!30]
\tikzstyle{toilet} = [fill=teal!30]
\input{manfreds_labyrinth_subgraph_weighted.tikz}
}
::::
:::

## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Untersucht den Dijkstra-Algorithmus

Öffne die Visualisierung unter **[https://bycs.link/yb8ey2](https://algorithms.discrete.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html)**.


\vspace{-0.1cm}
![](img/tum_graph_edit.png){.center height=70%}
\vspace{-0.1cm}

Lade unter \boldred{Graph erstellen} die Datei \boldred{labyrinth.txt} aus ByCS Drive hoch.

\begin{tikzpicture}[overlay, remember picture]
\node[draw=red, minimum width=1.1cm, minimum height=0.45cm, anchor=west, xshift=3.2cm, yshift=6.4cm] at (current page.south west) {};
\node[draw=red, minimum width=3cm, minimum height=0.5cm, anchor=west, xshift=9.6cm, yshift=2.95cm] at (current page.south west) {};
\node[anchor=west, xshift=0cm, yshift=3cm] at (current page.south west) {\includegraphics[keepaspectratio, width=4cm]{img/tum_visualisierung_qrcode.png}};
\end{tikzpicture}

## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Untersucht den Dijkstra-Algorithmus \hfill 7 min

Führe den Algorithmus **schrittweise** aus.

\begin{center}
\scalebox{0.8}{
\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, width=\textwidth]{img/tum_disjktra_ui.png}};
\node[draw=red, thick, minimum width=1.6cm, minimum height=0.3cm] at (4, 2.2) {};
\node[draw=red, thick, minimum width=4.5cm, minimum height=4.25cm] at (4.45, -0.25) {};
\end{tikzpicture}}
\end{center}

Achte dabei auf die Bedeutung der farblichen Markierungen.

## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Eigenschaften des Dijkstra-Algorithmus \hfill 5 min {.standout}

Teste dein Verständnis in Mebis:

Dijkstra Lücken

Fülle die Lücken und ergänze anschließend dein Arbeitsblatt.

## \faIcon{pencil-alt} Der Dijkstra-Algorithmus {.t}

\begin{merke}
Mithilfe des Dijkstra-Algorithmus kann in einem gewichteten Graphen \revealtexton{der kürzeste Pfad}{1}{2} zwischen zwei Knoten bzw. von einem Startknoten ausgehend zu allen anderen Knoten ermittelt werde.

Es wird immer die Kante verfolgt, welche die aktuell \revealtexton{kürzeste}{2}{3} Pfadlänge hat.
\end{merke}

\only<4->{
Dazu wird eine Warteschlange verwendet, in der die Knoten nach \revealtexton{Pfadlänge}{4}{5} sortiert sind.
}

\only<6->{
Um den günstigsten Weg zwischen dem Startknoten und einem zweiten Knoten konstruieren zu können, wird bei jeder Aktualisierung der gespeicherten Distanz zusätzlich der \revealtexton{Vorgänger}{6}{7} gespeichert.
}

## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Dijkstra-Algorithmus in Pseudocode \hfill 5 min {.standout}

Sortiere die Schritte des Dijktra-Algorithmus in Mebis:

Dijkstra Pseudocode

## \faIcon{pencil-alt} Drehe dein Arbeitsblatt um!

\small
\begin{center}
\input{pseudocode}
\end{center}

## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Hilfe für Manfred \hfill 5 min{.t}

::: {.columns align=center}
:::: {.column width=50%}
Bestimme mithilfe der Visualisierung des Dijkstra-Algorithmus und dem kompletten Graphen von Manfreds Labyrinth den **kürzesten Weg** für Manfred von seinem Heimkino (Raum 13/m) zu einer Toilette (Raum 2/b oder 14/n).
::::

:::: {.column width=50%}
\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, height=6cm]{img/manfreds_labyrinth_toilets.png}};
\end{tikzpicture}
::::
:::

\faIcon{pencil-alt} Notiert dabei die Reihenfolge in der der Dijkstra-Algorithmus alle Räume besucht.

## \faIcon{pencil-alt} Lösung: Hilfe für Manfred {.t}

::: {.columns align=center}
:::: {.column width=50%}
### Kürzester Weg zu einer Toilette
\only<2->{\textit{13/12/11/7/2} mit Länge} \only<3>{\textbf{19}}
::::

:::: {.column width=50%}
\begin{tikzpicture}[a/.style={->, line width=2pt, red}]
\node {\includegraphics[keepaspectratio, height=6cm]{img/manfreds_labyrinth_toilets.png}};
\only<2->{
  \draw[a] (2.55, -1.5) -- (1.8, -1);
  \draw[a] (1.2, -1) -- (-0.2, -0.8);
  \draw[a] (-0.5, -0.6) -- (-0.5, 0.2);
  \draw[a] (-0.5, 0.8) -- (-0.5, 1.6);
}
\end{tikzpicture}
::::
:::

## \faIcon{pencil-alt} Lösung: Hilfe für Manfred

\vspace{-0.5cm}
![](img/tum_disjktra_done.png){.center height=75%}

\vspace{-0.3cm}
### Besuchsreihenfolge der Räume
`13,12,10,16,11,9,15,6,8,4,3,7,5,2,14,1`

## {.standout}

Kürzeste Wege, wo braucht man das noch?

## 

\begin{center}
\begin{tikzpicture}[edge/.style = {}, path/.style={}, cycle/.style={}, blocked/.style={}]
\node[draw, thick] at (0, 0) {\includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{img/Copyrighted/navi.png}};
\node[draw, thick] at (4.75, 0) {\includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{img/Copyrighted/route.png}};
\node[draw, thick] at (9.5, 0) {\includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{img/Copyrighted/graph.png}};
%\node[draw, thick] at (9.5, 0) {\resizebox{4.5cm}{8cm}{\input{graph.tikz}}};
\end{tikzpicture}
\end{center}

## 

![](img/bike.png)

## \faIcon{pencil-alt} Arbeitsauftrag: Plane eine Radreise nach Venedig {.t}

::: {.columns align=center}
:::: {.column width=70%}
\resizebox{\textwidth}{!}{
\newcolumntype{C}{ >{\centering\arraybackslash} m{1.5cm} }
\newcolumntype{D}{ >{\centering\arraybackslash} m{1.4cm} }
 \renewcommand{\arraystretch}{1.5}% Spread rows out...
\begin{tabular}{c|C|D|D|D|D|D|D|c}
Ort & Traunstein \newline (Tra) & Innsbruck \newline (Is) & Millstatt \newline (M) & Trient \newline (Tri) & Innichen \newline (Ic) & Treviso \newline (Tre) & Venedig \newline (V) & Warteschlange\\
\hline
- & \only<2->{$0/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & Tra}\only<1>{&&&&&&&} \\
\hline
\only<3->{Tra} & \only<3->{\cellcolor{red!30}$0/-$} & \only<3->{$138/$Tra} & \only<3->{$211/$Tra} & & & & & \only<3->{Is, M} \\
\hline
\only<4->{Is} & & \only<4->{\cellcolor{red!30}$138/$Tra} & & \only<4->{$327/$Is} & \only<4->{$277/$Is} & & & \only<4->{M, Ic, Tri} \\
\hline
\only<5->{M} & & & \only<5->{\cellcolor{red!30}$211/$Tra} & & & & \only<5->{$489/$M} & \only<5->{Ic, Tri, V} \\
\hline
\only<6->{Ic} & & & & & \only<6->{\cellcolor{red!30}$277/$Is} & \only<6->{$434/$Ic} & & \only<6->{Tri, Tre, V} \\
\hline
\only<7->{Tri} & & & & \only<7->{\cellcolor{red!30}$327/$Is} & & & & \only<7->{Tre, V} \\
\hline
\only<8->{Tre} & & & & & & \only<8->{\cellcolor{red!30}$434/$Ic} & \only<8->{$472/$Tre} & \only<8->{V} \\
\hline
\only<9->{V} & & & & & & & \only<9->{\cellcolor{red!30}$472/$Tre} & \\
\hline
\end{tabular}
}
\begin{tikzpicture}[overlay, remember picture]
\only<12->{\draw[-Triangle, red, line width=1pt] (6.9, 0.2) -- (6.6, 0.4);}
\only<13->{\draw[-Triangle, red, line width=1pt] (6, 0.8) -- (5.5, 1.45);}
\only<14->{\draw[-Triangle, red, line width=1pt] (5, 1.75) -| (2.5, 2.3);}
\only<15->{\draw[-Triangle, red, line width=1pt] (2, 2.8) -- (1.8, 3);}
\end{tikzpicture}
::::

:::: {.column width=30%}
\resizebox{\textwidth}{!}{
\begin{tikzpicture}[
  graph vertex/.style={draw, ellipse, inner xsep=1pt, inner ysep=1mm},
  edge label/.style={fill=yellow!30},
  marked/.style={fill=blue!40},
  marked on/.style={alt=####1{marked}{}},
  active/.style={fill=red!40},
  active on/.style={alt=####1{active}{}},
]
\node[graph vertex, marked on=<3->, active on=<3>] (ts) {Traunstein};
\node[graph vertex, marked on=<4->, active on=<4>] (ib) at (-2.5, -2) {Innsbruck};
\node[graph vertex, marked on=<5->, active on=<5>] (ms) at (1.5, -2.5) {Millstatt};
\node[graph vertex, marked on=<6->, active on=<6>] (ic) at (-1, -3.5) {Innichen};
\node[graph vertex, marked on=<7->, active on=<7>] (tr) at (-3.5, -4) {Trient};
\node[graph vertex, marked on=<8->, active on=<8>] (tv) at (-2, -5.25) {Treviso};
\node[graph vertex, marked on=<9->, active on=<9>] (vd) at (0.5, -6) {Venedig};

\graph[edge quotes mid] {
  (ts) -- ["138" edge label] (ib),
  (ts) -- ["138" edge label] (ib),
  (ts) -- ["211" edge label] (ms),
  (ib) -- ["139" edge label] (ic),
  (ib) -- ["189" edge label] (tr),
  (ms) -- ["120" edge label] (ic),
  (tr) -- ["136" edge label] (tv),
  (ic) -- ["157" edge label] (tv),
  (ms) -- ["278" edge label] (vd),
  (tv) -- ["38" edge label] (vd),
};
\end{tikzpicture}
}
::::
:::

\only<10->{Kürzester Weg:} \only<15->{\textbf{Tra/Is/Ic/Tre/V}}

## \faIcon{pencil-alt} Hausaufgabe {.t}

Fülle die Tabelle zu dem Teilgraph von Manfreds Labyrinth auf deinem Arbeitsblatt.

::: {.columns}
:::: {.column width=70%}
\resizebox{\textwidth}{!}{
\renewcommand{\arraystretch}{1.5}% Spread rows out...
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c}
Raum & 2 & 4 & 7 & 9 & 10 & 11 & 12 & 13 & WS \\ \hline
& {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & \\[-0.1cm] \hline \only<-1>{&&&&&&&&&}\only<2->{- & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $0|-$ & 13} \\\hline
\only<-2>{&&&&&&&&&}\only<3->{13 & \unkn & \unkn & \unkn & \unkn & $5|13$ & \unkn & $4|13$ & \cur$0|-$ & 12, 10} \\\hline
\only<-3>{&&&&&&&&&}\only<4->{12 & \unkn & \unkn & \unkn & \unkn & $5|13$ & $9|12$ & \cur $4|13$ & \done $0|-$ & 10, 11} \\\hline
\only<-4>{&&&&&&&&&}\only<5->{10 & \unkn & \unkn & \unkn & $10|10$ & \cur $5|13$ & $9|12$ & \done $4|13$ & \done $0|-$ & 11, 9} \\\hline
\only<-5>{&&&&&&&&&}\only<6->{11 & \unkn & \unkn & $15|11$ &  $10|10$ & \done $5|13$ & \cur $9|12$ & \done $4|13$ & \done $0|-$ & 9, 7} \\\hline
\only<-6>{&&&&&&&&&}\only<7->{9 & \unkn & $14|9$ & $15|11$ & \cur $10|10$ & \done $5|13$ & \done $9|12$ & \done $4|13$ & \done $0|-$ & 4, 7} \\\hline
\only<-7>{\phantom{4} & \phantom{$20|4$} & \phantom{$14|9$} & \phantom{$15|11$} & \phantom{$10|10$} & \phantom{$5|9$} & \phantom{$9|12$} & \phantom{$4|13$} & \phantom{$0|-$} & \phantom{7, 2}}\only<8->{4 & $20|4$ & \cur $14|9$ & $15|11$ & \done $10|10$ & \done $5|13$ & \done $9|12$ & \done $4|13$ & \done $0|-$ & 7, 2} \\\hline
\only<-8>{&&&&&&&&&}\only<9->{7 & $19|7$ & \done $14|9$ & \cur $15|11$ & \done $10|10$ & \done $5|13$ & \done $9|12$ & \done $4|13$ & \done $0|-$ & 2 } \\\hline
\only<-9>{&&&&&&&&&}\only<10->{2 & \cur $19|7$  & \done $14|9$ & \done $15|11$ & \done $10|10$ & \done $5|13$ & \done $9|12$ & \done $4|13$ & \done $0|-$ &} \\
\end{tabular}
}
::::

:::: {.column width=30%}
\resizebox{\textwidth}{!}{
\begin{tikzpicture}[
  graph vertex/.style={draw, circle, minimum size=0.55cm, inner sep =0pt},
  edge label/.style={inner sep=0pt, circle, fill=white},
  marked/.style={fill=blue!40},
  marked on/.style={alt=####1{marked}{}},
  active/.style={fill=red!40},
  active on/.style={alt=####1{active}{}},
  toilet/.style={fill=teal!30},
  start/.style={draw=red, thick},
  start on/.style={alt=####1{start}{}},
]
\node[graph vertex, toilet, marked on=<10->, active on=<10>] (v2) at (2.50, 5.00) {2};
\node[graph vertex, marked on=<9->, active on=<9>] (v4) at (4.00, 4.15) {4};
\node[graph vertex, marked on=<8->, active on=<8>] (v7) at (2.80, 3.00) {7};
\node[graph vertex, marked on=<7->, active on=<7>] (v9) at (4.00, 2.55) {9};
\node[graph vertex, marked on=<5->, active on=<5>] (v10) at (5.50, 2.20) {10};
\node[graph vertex, marked on=<6->, active on=<6>] (v11) at (2.90, 1.50) {11};
\node[graph vertex, marked on=<4->, active on=<4>] (v12) at (4.20, 1.1) {12};
\node[graph vertex, start on=<1>, marked on=<3->, active on=<3>] (v13) at (5.50, .80) {13};

\graph[edge quotes mid] {
  (v2) --["6" edge label] (v4),
  (v4) --["4" edge label] (v9),
  (v2) --["4" edge label] (v7),
  (v7) --["5" edge label] (v9),
  (v7) --["6" edge label] (v11),
  (v9) --["8" edge label] (v11),
  (v9) --["5" edge label] (v10),
  (v10) --["9" edge label] (v11),
  (v11) --["5" edge label] (v12),
  (v12) --["4" edge label] (v13),
  (v10) --["5" edge label] (v13),
};
\end{tikzpicture}
}
::::
:::