Merge pull request #1 from AndreasFMueller/master

update

10 files changed, 987 insertions, 0 deletions

diff --git a/vorlesungen/slides/8/floyd-warshall/burgerking.png b/vorlesungen/slides/8/floyd-warshall/burgerking.png
new file mode 100644
index 0000000..cf4211d
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/burgerking.png
diff --git a/vorlesungen/slides/8/floyd-warshall/fw.tex b/vorlesungen/slides/8/floyd-warshall/fw.tex
new file mode 100644
index 0000000..99929fb
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/fw.tex
@@ -0,0 +1,680 @@
+%
+% fw.tex -- Durchführung des Floyd-Warshall Algorithmus
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+
+\definecolor{wegelb}{rgb}{1,0.6,0}
+\definecolor{weghell}{rgb}{1,0.9,0.6}
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\begin{columns}[t]
+\begin{column}{0.44\hsize}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+
+\def\r{2.2}
+\coordinate (A) at ({\r*cos(-54+0*72)},{\r*sin(-54+0*72)});
+\coordinate (C) at ({\r*cos(-54+1*72)},{\r*sin(-54+1*72)});
+\coordinate (D) at ({\r*cos(-54+2*72)},{\r*sin(-54+2*72)});
+\coordinate (B) at ({\r*cos(-54+3*72)},{\r*sin(-54+3*72)});
+\coordinate (E) at ({\r*cos(-54+4*72)},{\r*sin(-54+4*72)});
+
+\def\knoten#1#2#3{
+	\fill[color=#3] #1 circle[radius=0.3];
+	\draw[line width=1pt] #1 circle[radius=0.3];
+	\node at #1 {$#2$};
+}
+
+\def\kante#1#2#3{
+	\draw[->,line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm] #1 -- #2;
+	\fill[color=white,opacity=0.7] ($0.5*#1+0.5*#2$) circle[radius=0.22];
+	\node at ($0.5*#1+0.5*#2$) {$#3$};
+}
+
+% Wege über 1
+% 3--1--5
+\only<4>{
+	\draw[->,line width=7pt,color=red!50] 
+		(C)--(A)--(E);
+}
+
+% Wege über 2
+% 5--2--3
+\only<6>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(B)--(C);
+}
+% 5--2--4
+\only<7>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(B)--(D);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(E)--(D);
+}
+
+% Wege über 3
+% 2--3--1
+\only<9>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A);
+}
+% 2--3--5
+\only<10>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A)--(E);
+}
+% 4--3--1
+\only<11>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A);
+}
+% 4--3--5
+\only<12>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A)--(E);
+}
+% 5--3--1
+\only<13>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(B)--(C)--(A);
+}
+% 5--3--5
+\only<14>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(B)--(C)--(A)--(E);
+}
+
+% Wege über 4
+% 2--4--1
+\only<16>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(D)--(C)--(A);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(C)--(A);
+}
+% 2--4--3
+\only<17>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(D)--(C);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(C);
+}
+% 2--4--5
+\only<18>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(D)--(C)--(A)--(E);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(C)--(A)--(E);
+}
+% 5--4--1
+\only<19>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(D)--(C)--(A);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(E)--(B)--(C)--(A);
+}
+% 5--4--3
+\only<20>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(D)--(C);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(E)--(B)--(C);
+}
+% 5--4--5
+\only<21>{
+	\draw[->,line width=7pt,color=red!50] 
+		(E)--(D)--(C)--(A)--(E);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(E)--(B)--(C)--(A)--(E);
+}
+% 1--5--1
+\only<23>{
+	\draw[->,line width=7pt,color=red!50] 
+		(A)--(E)--(B)--(C)--(A);
+}
+% 1--5--2
+\only<24>{
+	\draw[->,line width=7pt,color=red!50] 
+		(A)--(E)--(B);
+}
+% 1--5--3
+\only<25>{
+	\draw[->,line width=7pt,color=red!50] 
+		(A)--(E)--(B)--(C);
+}
+% 1--5--4
+\only<26>{
+	\draw[->,line width=7pt,color=red!50] 
+		(A)--(E)--(D);
+}
+% 2--5--1
+\only<27>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A)--(E)--(D)--(C)--(A);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(C)--(A);
+}
+% 2--5--2
+\only<28>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A)--(E)--(B);
+}
+% 2--5--3
+\only<29>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A)--(E)--(D)--(C);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(C);
+}
+% 2--5--4
+\only<30>{
+	\draw[->,line width=7pt,color=red!50] 
+		(B)--(C)--(A)--(E)--(D);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(B)--(D);
+}
+% 3--5--1
+\only<31>{
+	\draw[->,line width=7pt,color=red!50] 
+		(C)--(A)--(E)--(D)--(C)--(A);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(C)--(A);
+}
+% 3--5--2
+\only<32>{
+	\draw[->,line width=7pt,color=red!50] 
+		(C)--(A)--(E)--(B);
+}
+% 3--5--3
+\only<33>{
+	\draw[->,line width=7pt,color=red!50] 
+		(C)--(A)--(E)--(B)--(C);
+}
+% 3--5--4
+\only<34>{
+	\draw[->,line width=7pt,color=red!50] 
+		(C)--(A)--(E)--(D);
+}
+% 4--5--1
+\only<35>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A)--(E)--(D)--(C)--(A);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(D)--(C)--(A);
+}
+% 4--5--2
+\only<36>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A)--(E)--(B);
+}
+% 4--5--3
+\only<37>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A)--(E)--(D)--(C);
+	\draw[->,line width=7pt,color=blue!50,dashed] 
+		(D)--(C);
+}
+% 4--5--4
+\only<38>{
+	\draw[->,line width=7pt,color=red!50] 
+		(D)--(C)--(A)--(E)--(D);
+}
+
+
+\uncover<40>{
+	\draw[->,color=red!50,line width=7pt]
+		(B)--(C)--(A)--(E)--(D);
+}
+
+\kante{(A)}{(E)}{1}
+\kante{(B)}{(C)}{2}
+\kante{(B)}{(D)}{13}
+\kante{(C)}{(A)}{3}
+\kante{(D)}{(C)}{6}
+\kante{(E)}{(B)}{5}
+\kante{(E)}{(D)}{6}
+
+\only<1>{
+	\knoten{(A)}{}{white}
+	\knoten{(B)}{}{white}
+	\knoten{(C)}{}{white}
+	\knoten{(D)}{}{white}
+	\knoten{(E)}{}{white}
+}
+
+\only<2->{
+	\knoten{(A)}{1}{white}
+	\knoten{(B)}{2}{white}
+	\knoten{(C)}{3}{white}
+	\knoten{(D)}{4}{white}
+	\knoten{(E)}{5}{white}
+}
+
+\only<4>{
+	\knoten{(A)}{1}{darkgreen!50}
+}
+\only<6-7>{
+	\knoten{(B)}{2}{darkgreen!50}
+}
+\only<9-14>{
+	\knoten{(C)}{3}{darkgreen!50}
+}
+\only<16-21>{
+	\knoten{(D)}{4}{darkgreen!50}
+}
+\only<23-38>{
+	\knoten{(E)}{5}{darkgreen!50}
+}
+
+\end{tikzpicture}
+\end{center}
+\begin{block}{Aufgabe}
+Finde den kürzesten Weg von 2 nach 4
+\end{block}
+\end{column}
+\begin{column}{0.5\hsize}
+\begin{center}
+\begin{tikzpicture}[>=latex,scale=0.8]
+
+\def\punkt#1#2{
+	({#2-0.5},{0.5-(#1)})
+}
+\def\punktoff#1#2{
+	({#2-0.7},{0.7-(#1)})
+}
+\def\feld#1#2#3{
+	\ifthenelse{\boolean{wegweiser}}{
+		\fill[color=white]
+			({#2-1},{1-#1}) rectangle ({#2-0.45},{0.45-#1});
+		\node at \punktoff{#1}{#2} {$#3$};
+	}{
+		\fill[color=white]
+			({#2-1},{1-#1}) rectangle ({#2},{-#1});
+		\node at \punkt{#1}{#2} {$#3$};
+	}
+}
+\def\verbindung#1#2#3{
+	\draw[->,line width=5pt,color=red!20,shorten >= 0.2cm,shorten <= 0.2cm]
+		\punkt{#1}{#2}--\punkt{#2}{#3};
+	\node at (5,-5.5) [left] {$#1\rightsquigarrow #2\rightsquigarrow #3$\strut};
+}
+\def\Infty{{}}
+\def\wegweiser#1#2#3{
+	\ifthenelse{\boolean{wegweiser}}{
+		\ifnum #2 = #3
+		\fill[color=weghell]
+			({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1});
+		\else
+		\fill[color=wegelb]
+			({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1});
+		\fi
+		\node at ({#2-0.25},{0.25-#1}) {\tiny #3};
+	}{}
+}
+
+% direkte Wege
+\uncover<3->{
+	\feld{1}{1}{\Infty}
+	\feld{1}{2}{\Infty}
+	\feld{1}{3}{\Infty}
+	\feld{1}{4}{\Infty}
+	\feld{1}{5}{1}
+	\wegweiser{1}{5}{5}
+
+	\feld{2}{1}{\Infty}
+	\feld{2}{2}{\Infty}
+	\feld{2}{3}{2}
+	\wegweiser{2}{3}{3}
+	\feld{2}{4}{13}
+	\wegweiser{2}{4}{4}
+	\feld{2}{5}{\Infty}
+
+	\feld{3}{1}{3}
+	\wegweiser{3}{1}{1}
+	\feld{3}{2}{\Infty}
+	\feld{3}{3}{\Infty}
+	\feld{3}{4}{\Infty}
+	\feld{3}{5}{\Infty}
+
+	\feld{4}{1}{\Infty}
+	\feld{4}{2}{\Infty}
+	\feld{4}{3}{6}
+	\wegweiser{4}{3}{3}
+	\feld{4}{4}{\Infty}
+	\feld{4}{5}{\Infty}
+
+	\feld{5}{1}{\Infty}
+	\feld{5}{2}{5}
+	\wegweiser{5}{2}{2}
+	\feld{5}{3}{\Infty}
+	\feld{5}{4}{6}
+	\wegweiser{5}{4}{4}
+	\feld{5}{5}{\Infty}
+}
+
+\uncover<3-3>{
+	\node at (-0.8,-5.5) [right] {direkte Verbindungen};
+}
+
+\uncover<4-4>{
+	\node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $1$:\strut};
+}
+
+% Wege über 1
+% 3-1-5
+\uncover<4>{
+	\verbindung{3}{1}{5}
+	\feld{3}{5}{\color{red}4}
+	\wegweiser{3}{5}{1}
+}
+\uncover<5->{
+	\feld{3}{5}{4}
+	\wegweiser{3}{5}{1}
+}
+
+\uncover<6-7>{
+	\node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $2$:\strut};
+}
+
+% Wege über 2
+% 5-2-3
+\uncover<6>{
+	\verbindung{5}{2}{3}
+	\feld{5}{3}{\color{red}7}
+	\wegweiser{5}{3}{2}
+}
+\uncover<7->{
+	\feld{5}{3}{7}
+	\wegweiser{5}{3}{2}
+}
+% 5-2-4
+\uncover<7>{
+	\verbindung{5}{2}{4}
+	\feld{5}{4}{\color{blue}6}
+}
+
+\uncover<9-14>{
+	\node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $3$:\strut};
+}
+
+% Wege über 3
+% 2-3-1
+\uncover<9>{
+	\verbindung{2}{3}{1}
+	\feld{2}{1}{\color{red}5}
+	\wegweiser{2}{1}{3}
+}
+\uncover<10->{
+	\feld{2}{1}{5}
+	\wegweiser{2}{1}{3}
+}
+% 2-3-5
+\uncover<10>{
+	\verbindung{2}{3}{5}
+	\feld{2}{5}{\color{red}6}
+	\wegweiser{2}{5}{3}
+}
+\uncover<11->{
+	\feld{2}{5}{6}
+	\wegweiser{2}{5}{3}
+}
+% 4-3-1
+\uncover<11>{
+	\verbindung{4}{3}{1}
+	\feld{4}{1}{\color{red}9}
+	\wegweiser{4}{1}{3}
+}
+\uncover<12->{
+	\feld{4}{1}{9}
+	\wegweiser{4}{1}{3}
+}
+% 4-3-5
+\uncover<12>{
+	\verbindung{4}{3}{5}
+	\feld{4}{5}{\color{red}10}
+	\wegweiser{4}{5}{3}
+}
+\uncover<13->{
+	\feld{4}{5}{10}
+	\wegweiser{4}{5}{3}
+}
+% 5-3-1
+\uncover<13>{
+	\verbindung{5}{3}{1}
+	\feld{5}{1}{\color{red}10}
+	\wegweiser{5}{1}{2}
+}
+\uncover<14->{
+	\feld{5}{1}{10}
+	\wegweiser{5}{1}{2}
+}
+% 5-3-5
+\uncover<14>{
+	\verbindung{5}{3}{5}
+	\feld{5}{5}{\color{red}11}
+	\wegweiser{5}{5}{2}
+}
+\uncover<15->{
+	\feld{5}{5}{11}
+	\wegweiser{5}{5}{2}
+}
+
+\uncover<16-21>{
+	\node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $4$:\strut};
+}
+
+% Wege über 4
+% 2-4-1
+\uncover<16>{
+	\verbindung{2}{4}{1}
+	\feld{2}{1}{\color{blue}5}
+}
+% 2-4-3
+\uncover<17>{
+	\verbindung{2}{4}{3}
+	\feld{2}{3}{\color{blue}2}
+}
+% 2-4-5
+\uncover<18>{
+	\verbindung{2}{4}{5}
+	\feld{2}{5}{\color{blue}6}
+}
+% 5-4-1
+\uncover<19>{
+	\verbindung{5}{4}{1}
+	\feld{5}{1}{\color{blue}10}
+}
+% 5-4-3
+\uncover<20>{
+	\verbindung{5}{4}{3}
+	\feld{5}{3}{\color{blue}7}
+}
+% 5-4-5
+\uncover<21>{
+	\verbindung{5}{4}{5}
+	\feld{5}{5}{\color{blue}11}
+}
+
+% Wege über 5
+\uncover<23-38>{
+	\node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $5$:\strut};
+}
+
+% Wege über 5
+% 1-5-1
+\uncover<23>{
+	\verbindung{1}{5}{1}
+	\feld{1}{1}{\color{red}11}
+	\wegweiser{1}{1}{5}
+}
+\uncover<24->{
+	\feld{1}{1}{11}
+	\wegweiser{1}{1}{5}
+}
+% 1-5-2
+\uncover<24>{
+	\verbindung{1}{5}{2}
+	\feld{1}{2}{\color{red}6}
+	\wegweiser{1}{2}{5}
+}
+\uncover<25->{
+	\feld{1}{2}{6}
+	\wegweiser{1}{2}{5}
+}
+% 1-5-3
+\uncover<25>{
+	\verbindung{1}{5}{3}
+	\feld{1}{3}{\color{red}8}
+	\wegweiser{1}{3}{5}
+}
+\uncover<26->{
+	\feld{1}{3}{8}
+	\wegweiser{1}{3}{5}
+}
+% 1-5-4
+\uncover<26>{
+	\verbindung{1}{5}{4}
+	\feld{1}{4}{\color{red}7}
+	\wegweiser{1}{4}{5}
+}
+\uncover<27->{
+	\feld{1}{4}{7}
+	\wegweiser{1}{4}{5}
+}
+% 2-5-1
+\uncover<27>{
+	\verbindung{2}{5}{1}
+	\feld{2}{1}{\color{blue}5}
+}
+% 2-5-2
+\uncover<28>{
+	\verbindung{2}{5}{2}
+	\feld{2}{2}{\color{red}11}
+	\wegweiser{2}{2}{3}
+}
+\uncover<29->{
+	\feld{2}{2}{11}
+	\wegweiser{2}{2}{3}
+}
+% 2-5-3
+\uncover<29>{
+	\verbindung{2}{5}{3}
+	\feld{2}{3}{\color{blue}2}
+}
+% 2-5-4
+\uncover<30>{
+	\verbindung{2}{5}{4}
+	\feld{2}{4}{\color{red}12}
+	\wegweiser{2}{4}{3}
+}
+\uncover<31->{
+	\feld{2}{4}{12}
+	\wegweiser{2}{4}{3}
+}
+% 3-5-1
+\uncover<31>{
+	\verbindung{3}{5}{1}
+	\feld{3}{1}{\color{blue}3}
+}
+% 3-5-2
+\uncover<32>{
+	\verbindung{3}{5}{2}
+	\feld{3}{2}{\color{red}9}
+	\wegweiser{3}{2}{1}
+}
+\uncover<33->{
+	\feld{3}{2}{9}
+	\wegweiser{3}{2}{1}
+}
+% 3-5-3
+\uncover<33>{
+	\verbindung{3}{5}{3}
+	\feld{3}{3}{\color{red}11}
+	\wegweiser{3}{3}{1}
+}
+\uncover<34->{
+	\feld{3}{3}{11}
+	\wegweiser{3}{3}{1}
+}
+% 3-5-4
+\uncover<34>{
+	\verbindung{3}{5}{4}
+	\feld{3}{4}{\color{red}10}
+	\wegweiser{3}{4}{1}
+}
+\uncover<35->{
+	\feld{3}{4}{10}
+	\wegweiser{3}{4}{1}
+}
+% 4-5-1
+\uncover<35>{
+	\verbindung{4}{5}{1}
+	\feld{4}{1}{\color{blue}9}
+}
+% 4-5-2
+\uncover<36>{
+	\verbindung{4}{5}{2}
+	\feld{4}{2}{\color{red}15}
+	\wegweiser{4}{2}{3}
+}
+\uncover<37->{
+	\feld{4}{2}{15}
+	\wegweiser{4}{2}{3}
+}
+% 4-5-3
+\uncover<37>{
+	\verbindung{4}{5}{3}
+	\feld{4}{3}{\color{blue}6}
+}
+% 4-5-4
+\uncover<38>{
+	\verbindung{4}{5}{4}
+	\feld{4}{4}{\color{red}16}
+	\wegweiser{4}{4}{3}
+}
+\uncover<39->{
+	\feld{4}{4}{16}
+	\wegweiser{4}{4}{3}
+}
+
+
+\uncover<3->{
+
+	\foreach \x in {0,...,5}{
+		\draw[line width=0.7pt] (\x,0.8)--(\x,-5);
+	}
+	\foreach \y in {0,...,-5}{
+		\draw[line width=0.7pt] (-0.8,\y)--(5,\y);
+	}
+	\draw[line width=1.4pt] (0,0)--(5,0)--(5,-5)--(0,-5)--cycle;
+
+	\node at (0.5,0.5) {$1$};
+	\node at (1.5,0.5) {$2$};
+	\node at (2.5,0.5) {$3$};
+	\node at (3.5,0.5) {$4$};
+	\node at (4.5,0.5) {$5$};
+
+	\node at (-0.5,-0.5) {$1$};
+	\node at (-0.5,-1.5) {$2$};
+	\node at (-0.5,-2.5) {$3$};
+	\node at (-0.5,-3.5) {$4$};
+	\node at (-0.5,-4.5) {$5$};
+}
+
+\end{tikzpicture}
+\end{center}
+
+\uncover<40>{
+	\vspace{-22pt}
+	\begin{block}{Lösung}
+	Der kürzeste Weg von 2 nach 4 ist 2---3---1---5---4
+	\end{block}
+}
+
+\end{column}
+\end{columns}
+
+\egroup
diff --git a/vorlesungen/slides/8/floyd-warshall/iteration.tex b/vorlesungen/slides/8/floyd-warshall/iteration.tex
new file mode 100644
index 0000000..d7e782d
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/iteration.tex
@@ -0,0 +1,14 @@
+%
+% iteration.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+\newboolean{wegweiser}
+\begin{frame}[fragile]
+\frametitle{Floyd-Warshall: Iteration}
+\setboolean{wegweiser}{false}
+\input{../slides/8/floyd-warshall/fw.tex}
+
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/floyd-warshall/macdonalds.png b/vorlesungen/slides/8/floyd-warshall/macdonalds.png
new file mode 100644
index 0000000..c442dfb
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/macdonalds.png
diff --git a/vorlesungen/slides/8/floyd-warshall/problem.tex b/vorlesungen/slides/8/floyd-warshall/problem.tex
new file mode 100644
index 0000000..93f8229
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/problem.tex
@@ -0,0 +1,146 @@
+%
+% graph.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}[fragile]
+\frametitle{Problem: Kürzeste Wege}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+\def\blob#1#2#3{
+	\fill[color=#3] #1 circle[radius=0.2];
+	\draw[line width=0.7pt] #1 circle[radius=0.2];
+	\node at #1 {{\tiny #2}};
+}
+
+\def\kante#1#2{
+	\draw[line width=0.7pt,shorten >= 0.2,shorten >= 0.2] #1 -- #2 ;
+}
+
+\def\a{72}
+\def\r{1.0}
+\def\R{2.0}
+\def\RR{3.5}
+
+\coordinate (A1) at ({\r*cos(0*\a)},{\r*sin(0*\a)});
+\coordinate (B1) at ({\r*cos(1*\a)},{\r*sin(1*\a)});
+\coordinate (C1) at ({\r*cos(2*\a)},{\r*sin(2*\a)});
+\coordinate (D1) at ({\r*cos(3*\a)},{\r*sin(3*\a)});
+\coordinate (E1) at ({\r*cos(4*\a)},{\r*sin(4*\a)});
+
+\coordinate (F1) at ({\R*cos(0*\a)},{\R*sin(0*\a)});
+\coordinate (G1) at ({\R*cos(1*\a)},{\R*sin(1*\a)});
+\coordinate (H1) at ({\R*cos(2*\a)},{\R*sin(2*\a)});
+\coordinate (I1) at ({\R*cos(3*\a)},{\R*sin(3*\a)});
+\coordinate (J1) at ({\R*cos(4*\a)},{\R*sin(4*\a)});
+
+\coordinate (K1) at ({\RR*cos(0.5*\a)},{\RR*sin(0.5*\a)});
+\coordinate (L1) at ({\RR*cos(1.5*\a)},{\RR*sin(1.5*\a)});
+\coordinate (M1) at ({\RR*cos(2.5*\a)},{\RR*sin(2.5*\a)});
+\coordinate (N1) at ({\RR*cos(3.5*\a)},{\RR*sin(3.5*\a)});
+\coordinate (O1) at ({\RR*cos(4.5*\a)},{\RR*sin(4.5*\a)});
+
+\kante{(A1)}{(C1)}
+\kante{(C1)}{(E1)}
+\kante{(E1)}{(B1)}
+\kante{(B1)}{(D1)}
+\kante{(D1)}{(A1)}
+
+\kante{(F1)}{(G1)}
+\kante{(G1)}{(H1)}
+\kante{(H1)}{(I1)}
+\kante{(I1)}{(J1)}
+\kante{(J1)}{(F1)}
+
+\kante{(A1)}{(F1)}
+\kante{(B1)}{(G1)}
+\kante{(C1)}{(H1)}
+\kante{(D1)}{(I1)}
+\kante{(E1)}{(J1)}
+
+\kante{(K1)}{(L1)}
+\kante{(L1)}{(M1)}
+\kante{(M1)}{(N1)}
+\kante{(N1)}{(O1)}
+\kante{(O1)}{(K1)}
+
+\kante{(F1)}{(K1)}
+\kante{(G1)}{(L1)}
+\kante{(H1)}{(M1)}
+\kante{(I1)}{(N1)}
+\kante{(J1)}{(O1)}
+
+\kante{(F1)}{(O1)}
+\kante{(G1)}{(K1)}
+\kante{(H1)}{(L1)}
+\kante{(I1)}{(M1)}
+\kante{(J1)}{(N1)}
+
+\uncover<2>{
+	\draw[line width=2pt,color=red] (M1)--(H1)--(G1)--(B1);
+}
+
+\uncover<3>{
+	\draw[line width=2pt,color=red] (M1)--(L1)--(G1)--(B1);
+}
+
+\uncover<4>{
+	\draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(B1);
+}
+
+\uncover<5>{
+	\draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(A1)--(F1);
+}
+
+\uncover<6->{
+	\draw[line width=2pt,color=red] (M1)--(I1)--(J1)--(F1);
+}
+
+\uncover<2-4>{
+	\blob{(B1)}{1}{red!20}
+	\blob{(M1)}{12}{red!20}
+}
+\uncover<5-8>{
+	\blob{(M1)}{1}{red!20}
+	\blob{(F1)}{12}{red!20}
+}
+
+\blob{(A1)}{0}{white}
+\uncover<1>{
+	\blob{(B1)}{1}{white}
+}
+\uncover<5-8>{
+	\blob{(B1)}{12}{white}
+}
+\blob{(C1)}{2}{white}
+\blob{(D1)}{3}{white}
+\blob{(E1)}{4}{white}
+\uncover<1-4>{
+	\blob{(F1)}{5}{white}
+}
+\blob{(G1)}{6}{white}
+\blob{(H1)}{7}{white}
+\blob{(I1)}{8}{white}
+\blob{(J1)}{9}{white}
+\blob{(K1)}{10}{white}
+\blob{(L1)}{11}{white}
+\uncover<1>{
+	\blob{(M1)}{12}{white}
+}
+\blob{(N1)}{13}{white}
+\blob{(O1)}{14}{white}
+
+\node at (6,0) {\begin{minipage}{5cm}
+\begin{itemize}
+\item<3-> Nicht eindeutig
+\item<5-> geradeste Wege sind nicht unbedingt die kürzesten
+\item<7-> Gewichtung der Kanten
+($\text{Schnellstrassen}\ne\text{Feldwege}$)
+\item<8-> Orientierung der Kanten?
+\end{itemize}
+\end{minipage}};
+
+\end{tikzpicture}
+\end{center}
+\end{frame}
diff --git a/vorlesungen/slides/8/floyd-warshall/rekursion.tex b/vorlesungen/slides/8/floyd-warshall/rekursion.tex
new file mode 100644
index 0000000..c664e41
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/rekursion.tex
@@ -0,0 +1,108 @@
+%
+% rekursion.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}[fragile]
+\frametitle{Rekursion}
+\vspace{-20pt}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+\def\blob#1#2#3{
+        \fill[color=#3] #1 circle[radius=0.3];
+        \draw[line width=0.7pt] #1 circle[radius=0.3];
+        \node at #1 {{#2}};
+}
+
+\def\kante#1#2{
+        \draw[line width=0.7pt,shorten >= 0.3,shorten >= 0.3] #1 -- #2 ;
+}
+
+\coordinate (A) at (0,0);
+\coordinate (B1) at (2,2);
+\coordinate (B2) at (2,1);
+\coordinate (B3) at (2,0);
+\coordinate (B4) at (2,-1);
+\coordinate (B5) at (2,-2);
+
+\draw[line width=1.9pt,color=gray] (A)--(B1);
+\draw[line width=1.9pt,color=gray] (A)--(B2);
+\draw[line width=1.9pt,color=gray] (A)--(B3);
+\draw[line width=1.9pt,color=gray] (A)--(B4);
+\draw[line width=1.9pt,color=gray] (A)--(B5);
+
+\coordinate (Z) at (10,0);
+
+\begin{scope}
+\clip (2,-2.3) rectangle (10,2.3);
+\foreach \y in{-10,...,10}{
+	\draw[line width=1.9pt,color=gray]
+		(2,\y)--(10,{\y-8});
+	\draw[line width=1.9pt,color=gray]
+		(2,\y)--(10,{\y+8});
+}
+\end{scope}
+
+\uncover<2>{
+\draw[line width=4pt,color=red] (A)--(B1)--(5,-1)--(8,2)--(Z);
+}
+
+\uncover<3>{
+\draw[line width=4pt,color=red] (A)--(B2)--(3,0)--(4,1)--(5,0)--(6,1)--(8.5,-1.5)--(Z);
+}
+
+\uncover<4>{
+\draw[line width=4pt,color=red] (A)--(B3)--(2.5,0.5)--(3.5,-0.5)--(5,1.0)--(7,-1)--(9,1)--(Z);
+}
+
+\uncover<5>{
+\draw[line width=4pt,color=red] (A)--(B4)--(3,0)--(4,1)--(5,0)--(6,1)--(7,0)
+	--(6.0,-1.0)--(7,-2)--(7.5,-1.5)--(7,-1)--(7.5,-0.5)
+	--(8.5,-1.5)--(Z);
+}
+
+\uncover<6->{
+	\draw[line width=4pt,color=red] (A)--(B5)--(6,2);
+}
+\uncover<7->{
+	\draw[line width=4pt,color=red] (6,2)--(7,1)--(5,-1);
+}
+\uncover<8->{
+	\draw[line width=4pt,color=red] (5,-1)--(6,-2)--(8,0)--(9,-1);
+}
+\uncover<9->{
+	\draw[line width=4pt,color=red] (9,-1)--(Z);
+}
+
+\blob{(A)}{$A$}{red!20}
+\blob{(B1)}{$B_1$}{white}
+\blob{(B2)}{$B_2$}{white}
+\blob{(B3)}{$B_3$}{white}
+\blob{(B4)}{$B_4$}{white}
+\blob{(B5)}{$B_5$}{white}
+
+\blob{(Z)}{$Z$}{red!20}
+
+\uncover<6->{
+	\node at (6,2) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/macdonalds.png}};
+}
+
+\uncover<7->{
+	\node at (5,-1) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/starbucks.png}};
+}
+
+\uncover<8->{
+	\node at (9,-1) {\includegraphics[width=2cm]{../slides/8/floyd-warshall/burgerking.png}};
+}
+
+\end{tikzpicture}
+\end{center}
+
+\begin{block}{Abstieg}
+Für den kürzesten Weg von $A$ nach $Z$ suche denjenigen Nachbarn $B_i$
+von $A$, der den kürzesten Weg von $B_i$ nach $Z$ hat.
+\uncover<7->{$\Rightarrow$ wir brauchen {\color{red}alle} kürzesten Wege!}
+\end{block}
+
+\end{frame}
diff --git a/vorlesungen/slides/8/floyd-warshall/starbucks.png b/vorlesungen/slides/8/floyd-warshall/starbucks.png
new file mode 100644
index 0000000..a28dbf7
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/starbucks.png
diff --git a/vorlesungen/slides/8/floyd-warshall/wege.tex b/vorlesungen/slides/8/floyd-warshall/wege.tex
new file mode 100644
index 0000000..7ff62a1
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/wege.tex
@@ -0,0 +1,26 @@
+%
+% wege.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}
+\frametitle{Wege statt Weglänge?}
+\begin{columns}[t]
+\begin{column}{0.48\hsize}
+\begin{block}{Wege speichern?}
+\uncover<3->{Es reicht, einen Wegweiser zum nächsten Knoten zu speichern}
+\end{block}
+\begin{center}
+\begin{tikzpicture}[>=latex]
+
+\end{tikzpicture}
+\end{center}
+\end{column}
+\begin{column}{0.48\hsize}
+\uncover<2->{%
+\begin{center}
+\includegraphics[width=\hsize]{../slides/8/floyd-warshall/wegweiser.jpg}
+\end{center}}%
+\end{column}
+\end{columns}
+\end{frame}
diff --git a/vorlesungen/slides/8/floyd-warshall/wegiteration.tex b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex
new file mode 100644
index 0000000..84ec679
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex
@@ -0,0 +1,13 @@
+%
+% wegiteration.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\bgroup
+\newboolean{wegweiser}
+\begin{frame}[fragile]
+\frametitle{Floyd-Warshall: Wegweiser}
+\setboolean{wegweiser}{true}
+\input{../slides/8/floyd-warshall/fw.tex}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg
new file mode 100644
index 0000000..33aebe3
--- /dev/null
+++ b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg