diff options
Diffstat (limited to 'vorlesungen/slides/8/floyd-warshall/fw.tex')
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/fw.tex | 680 |
1 files changed, 680 insertions, 0 deletions
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 |