From ac7015feefad911eb609c5ab032d234cb654ef4d Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Sat, 13 Mar 2021 10:48:55 +0100
Subject: add new slides

---
 vorlesungen/slides/8/floyd-warshall/fw.tex | 680 +++++++++++++++++++++++++++++
 1 file changed, 680 insertions(+)
 create mode 100644 vorlesungen/slides/8/floyd-warshall/fw.tex

(limited to 'vorlesungen/slides/8/floyd-warshall/fw.tex')

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
-- 
cgit v1.2.1