add dijkstra slides

20 files changed, 617 insertions, 0 deletions

diff --git a/Info/11/NTG/1/Dijkstra/.gitignore b/Info/11/NTG/1/Dijkstra/.gitignore
new file mode 100644
index 00000000..90104180
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/.gitignore
@@ -0,0 +1,4 @@
+AB_*.pdf
+pseudocode.pdf
+radtour.pdf
+radtour.png
diff --git a/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra.jpg b/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra.jpg
new file mode 100644
index 00000000..16f2d773
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra.jpg
diff --git a/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra_cutout.png b/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra_cutout.png
new file mode 100644
index 00000000..1f6d3df7
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/Edsger_Wybe_Dijkstra_cutout.png
diff --git a/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG.jpg b/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG.jpg
new file mode 100644
index 00000000..49efb8d3
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG.jpg
diff --git a/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG_cutout.png b/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG_cutout.png
new file mode 100644
index 00000000..c1171597
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/Stoppuhr_digital_noBG_cutout.png
diff --git a/Info/11/NTG/1/Dijkstra/img/bike.png b/Info/11/NTG/1/Dijkstra/img/bike.png
new file mode 120000
index 00000000..5d64ff4b
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/bike.png
@@ -0,0 +1 @@
+../../Intro/img/bike.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfred_cut_out.png b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out.png
new file mode 120000
index 00000000..4a370da5
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfred_cut_out.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_autum.png b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_autum.png
new file mode 120000
index 00000000..4e5a9b53
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_autum.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfred_cut_out_autum.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad.png b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad.png
new file mode 120000
index 00000000..50df8c04
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfred_cut_out_sad.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad_under_water.png b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad_under_water.png
new file mode 120000
index 00000000..a7ceae23
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfred_cut_out_sad_under_water.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfred_cut_out_sad_under_water.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_subgraph_toilets.png b/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_subgraph_toilets.png
new file mode 120000
index 00000000..1fbb8a17
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_subgraph_toilets.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfreds_labyrinth_subgraph_toilets.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_toilets.png b/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_toilets.png
new file mode 120000
index 00000000..5a542766
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/manfreds_labyrinth_toilets.png
@@ -0,0 +1 @@
+../../ManfredsLabyrinth/manfreds_labyrinth_toilets.png
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/img/tum_disjktra_done.png b/Info/11/NTG/1/Dijkstra/img/tum_disjktra_done.png
new file mode 100644
index 00000000..b6e648e5
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/tum_disjktra_done.png
diff --git a/Info/11/NTG/1/Dijkstra/img/tum_disjktra_ui.png b/Info/11/NTG/1/Dijkstra/img/tum_disjktra_ui.png
new file mode 100644
index 00000000..3653f9e0
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/tum_disjktra_ui.png
diff --git a/Info/11/NTG/1/Dijkstra/img/tum_visualisierung_qrcode.png b/Info/11/NTG/1/Dijkstra/img/tum_visualisierung_qrcode.png
new file mode 100644
index 00000000..40cc9090
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/img/tum_visualisierung_qrcode.png
diff --git a/Info/11/NTG/1/Dijkstra/manfreds_labyrinth_subgraph_weighted.tikz b/Info/11/NTG/1/Dijkstra/manfreds_labyrinth_subgraph_weighted.tikz
new file mode 120000
index 00000000..d8881796
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/manfreds_labyrinth_subgraph_weighted.tikz
@@ -0,0 +1 @@
+../ManfredsLabyrinth/manfreds_labyrinth_subgraph_weighted.tikz
\ No newline at end of file
diff --git a/Info/11/NTG/1/Dijkstra/pseudocode.tex b/Info/11/NTG/1/Dijkstra/pseudocode.tex
new file mode 100644
index 00000000..a0206c82
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/pseudocode.tex
@@ -0,0 +1,50 @@
+\documentclass{standalone}
+\usepackage[ngerman]{babel}
+\usepackage{amsmath}
+\usepackage[most]{tcolorbox}
+\usetikzlibrary{decorations.pathmorphing}
+\tikzset{decoration={random steps, segment length=5mm, amplitude=0.6pt}}
+\usepackage{xcolor}
+\newcommand{\revealtexton}[3]{#1}
+
+\newtcolorbox{pseudocode}{
+  coltitle=white,
+  colbacktitle=gray!30!black,
+  colframe=gray!30!black,
+  enhanced,
+  title=\bfseries {\large P}SEUDOCODE,
+  attach boxed title to top right={yshift=-0.28cm, xshift=-5mm},
+  frame code={
+    \draw[decorate, draw=gray!30!black] (frame.north east) rectangle (frame.south west);
+  },
+}
+\newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
+\usepackage{changepage}
+
+\begin{document}
+\begin{pseudocode}
+\textvtt{Weise allen Knoten die beiden Eigenschaften „Distanz“ und „Vorgänger“ zu.
+Initialisiere die Distanz des Startknoten mit \revealtexton{0}{1}{2} und die aller anderen Knoten mit \revealtexton{$\infty$.}{2}{3}}
+\vspace{0.1cm}
+
+\textvtt{Füge den Startknoten der Warteschlange hinzu.}
+\vspace{0.1cm}
+
+\textvtt{Solange die Warteschlange nicht leer ist ...}
+\vspace{0.1cm}
+
+\begin{adjustwidth}{0.5cm}{}
+\textvtt{Wähle den Knoten mit \revealtexton{minimaler}{3}{4} (aufsummierter) Distanz als aktuellen Knoten und entferne ihn aus der Warteschlange.}
+\vspace{0.1cm}
+
+\textvtt{Markiere diesen Knoten.}
+\vspace{0.1cm}
+
+\textvtt{Berechne für alle \revealtexton{unmarkierten}{3}{4} Nachbarn die Gesamtdistanz des Pfades zum Startknoten ($\text{Kantengewicht} + \text{Distanz des aktuellen Knotens}$).}
+\vspace{0.1cm}
+
+\textvtt{Ist dieser Wert kleiner als die für diesen Nachbarn gespeicherte Distanz, aktualisiere sie und speichere den \revealtexton{aktuellen Knoten}{4}{5} als Vorgänger.}
+\end{adjustwidth}
+\end{pseudocode}
+\end{document}
+
diff --git a/Info/11/NTG/1/Dijkstra/radtour.tex b/Info/11/NTG/1/Dijkstra/radtour.tex
new file mode 100644
index 00000000..fe18dc12
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/radtour.tex
@@ -0,0 +1,6 @@
+\documentclass{standalone}
+\usepackage{tikz}
+\usetikzlibrary{graphs, shapes, quotes}
+\begin{document}
+\input{radtour.tikz}
+\end{document}
diff --git a/Info/11/NTG/1/Dijkstra/radtour.tikz b/Info/11/NTG/1/Dijkstra/radtour.tikz
new file mode 100644
index 00000000..9869869e
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/radtour.tikz
@@ -0,0 +1,25 @@
+\begin{tikzpicture}[
+  graph vertex/.style={draw, ellipse, inner xsep=1pt, inner ysep=1mm},
+  edge label/.style={fill=yellow!30}
+]
+\node[graph vertex] (ts) {Traunstein};
+\node[graph vertex] (ib) at (-2.5, -2) {Innsbruck};
+\node[graph vertex] (ms) at (1.5, -2.5) {Millstatt};
+\node[graph vertex] (ic) at (-1, -3.5) {Innichen};
+\node[graph vertex] (tr) at (-3.5, -4) {Trient};
+\node[graph vertex] (tv) at (-2, -5.25) {Treviso};
+\node[graph vertex] (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}
diff --git a/Info/11/NTG/1/Dijkstra/slides.md b/Info/11/NTG/1/Dijkstra/slides.md
new file mode 100644
index 00000000..74b9c42d
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/slides.md
@@ -0,0 +1,524 @@
+---
+header-includes: |
+    \usepackage{ulem}
+    \makeatletter
+    \beamer@ignorenonframefalse
+    \makeatother
+    
+    \usetikzlibrary{graphs, shapes, quotes}
+    \usetikzlibrary{overlay-beamer-styles}
+    
+    \newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
+    \usepackage{changepage}
+    \usepackage{standalone}
+    \newcommand\revealtexton[3]{\textbf{\only<-#2>{\textcolor{bg}{#1}}\only<#3->{\textcolor{red}{#1}}}}
+---
+
+## {.standout}
+Herzlich Willkommen!
+
+Du brauchst dich heute nicht anmelden.
+
+Die Computer sind an, aber gesperrt.
+
+Tablets bitte in der Tasche lassen!
+
+## \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:
+
+* Attribut der Klasse `Knoten`
+* Array um die Markierungen zu speichern
+
+::: {.columns}
+:::: {.column width=50%}
+\begin{center}
+\begin{tikzpicture}
+\begin{class}[]{Knoten}{0, 0}
+\attribute{String bezeichnung}
+\attribute{boolean markiert}
+\operation{...}
+\end{class}
+\end{tikzpicture}
+\end{center}
+::::
+
+:::: {.column width=50%}
+\resizebox{0.85\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.
+`}`{=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]{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 (9, -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]{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-Algortihmus \hfill 7 min
+
+Lies die Erklärung zu jedem Schritt und führe den Algorithmus **schrittweise** aus.
+
+\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}
+
+## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Eigenschaften des Dijkstra-Algortihmus \hfill 5 min {.standout}
+
+Teste dein Verständnis unter:
+
+[https://schule.muhq.space/dijkstra](https://schule.muhq.space/dijkstra)
+
+Fülle die Lücken und ergänze anschließend dein Arbeitsblatt.
+
+## \faIcon{pencil-alt} Der Dijkstra-Algorithmus
+
+\begin{merke}
+Mithilfe des Dijkstra-Algortihmus 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}
+
+## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Dijkstra-Algortihmus in Pseudocode \hfill 5 min {.standout}
+
+Sortiere die Schritte des Dijktra-Algorithmus unter
+
+[https://schule.muhq.space/dijkstra2](https://schule.muhq.space/dijkstra2)
+
+## \faIcon{pencil-alt} Drehe dein Arbeitsblatt um!
+
+\small
+\input{pseudocode.tex}
+
+## \faIcon{desktop}/\faIcon{hands-helping} Arbeitsauftrag: Hilfe für Manfred \hfill 3 min{.t}
+
+::: {.columns align=center}
+:::: {.column width=50%}
+Bestimme mithilfe der Visualisierung des Dijkstra-Algortihmus 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-Algortihmus 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
+
+::: {.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->{Ic} & & & & \only<7->{\cellcolor{red!30}$327/$Is} & & & & \only<7->{Tre, V} \\
+\hline
+\only<8->{Ic} & & & & & & \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}
+}
+::::
+
+:::: {.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}
+}
+::::
+:::
+
+## \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.2cm] \hline 
+\only<2->{- & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $0|-$ & 13}
+\only<3->{\\\hline 13 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $5|9$  & $\infty|-$ & $\infty|-$ & \cellcolor{red!30}$12|9$ & 12, 10}
+\only<4->{\\\hline 12 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $10|10$ & $5|9$ & $9|12$ & \cellcolor{red!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 10, 11}
+\only<5->{\\\hline 10 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $10|10$ & \cellcolor{red!30} $5|9$ & $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 11, 9}
+\only<6->{\\\hline 11 & $\infty|-$ & $\infty|-$ & $15|11$ &  $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{red!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 9, 7}
+\only<7->{\\\hline 9 & $\infty|-$ & $14|9$ & $15|11$ & \cellcolor{red!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 7, 4}
+\only<9->{\\\hline 4 & $20|4$ & \cellcolor{red!30} $14|9$ & \cellcolor{gray!30} $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 4, 2}
+\only<8->{\\\hline 7 & $19|7$ & \cellcolor{gray!30} $14|9$ & \cellcolor{red!30} $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 2 }
+\only<10->{\\\hline 2 & \cellcolor{red!30} $19|7$  & \cellcolor{gray!30} $14|4$ & \cellcolor{gray!30} $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $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}
+}
+::::
+:::
+
+## {.standout}
+Schöne Ferien!