diff options
Diffstat (limited to 'sheet.tex')
| -rw-r--r-- | sheet.tex | 562 |
1 files changed, 193 insertions, 369 deletions
@@ -10,10 +10,14 @@ ]{geometry} \usepackage{amsmath} \usepackage{amsfonts} +\usepackage{makecell} \usepackage{multicol} \usepackage[noend]{algorithm2e} \usepackage[utf8]{inputenc} \usepackage{fancyhdr} +\usepackage{tikz} +\usetikzlibrary{arrows,automata,positioning, graphs, graphdrawing} +\usegdlibrary {trees} \usepackage{hyperref} \hypersetup{ colorlinks=true, @@ -33,397 +37,217 @@ \fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/}} \fancyfoot{} \fancyfoot[R]{\thepage} -\section{Laufzeit} +\newenvironment{definition}[1]{\noindent\textbf{#1:}}{} +\section{Chomsky-Hierarchie} \hspace*{-.5cm} -\begin{tabular}{ l l l l } - Notations & Asymptotischer Vergleich & Formale Definition & Grenzen \\ - $f(n) \in \omega(g(n))$& - $f(n)$ wächst schneller als $g(n)$ & - $\forall c \exists n_0 \forall n > n_0 f(n) > c \cdot g(n)$ & - $$$\lim\sup\limits_{n \rightarrow \infty}\frac{f}{g} = \infty$$$ \\ - - $f(n) \in \Omega(g(n))$ & - $f(n)$ wächst min. so schnell wie $g(n)$ & - $\exists c \exists n_0 \forall n > n_0 c \cdot f(n) \leq g(n)$ & - $$$0 < \liminf\limits_{n \rightarrow \infty}\frac{f}{g} \leq \infty$$$ \\ - - \( f(n) \in \Theta(g(n)) \) & - $f(n)$ und $g(n)$ wachsen gleich schnell & - $f(n) \in \mathcal{O}(g(n)) \wedge f(n) \in \Omega(g(n))$ & - $$$0 < \lim\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\ - - \( f(n) \in \mathcal{O}(g(n)) \) & - $f(n)$ wächst max. so schnell wie $g(n)$ & - $\exists c \exists n_0 \forall n > n_0 f(n) \leq c \cdot g(n)$ & - $$$0 \leq \limsup\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\ - - \( f(n) \in o(g(n)) \) & - $f(n)$ wächst langsamer als $g(n)$ & - $\forall c \exists n_0 \forall n > n_0 c \cdot f(n) < g(n)$ & - $$$\lim\limits_{n \rightarrow \infty} \frac{f}{g} = \infty$$$ \\ - -\end{tabular} - -\subsection{Vergleich} -\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} - $1$ & $\log^*n$ & $\log n$ & $\log^2n$ & $\sqrt[3]{n}$ & - $\sqrt{n}$ & $n$ & $n^2$ & $n^3$ & $n^{\log n}$ & - $2^{\sqrt{n}}$ & $2^n$ & $3^n$ & $4^n$ & $n!$ & $2^{n^2}$ +\begin{tabular}{ l l l l l } + Chomsky-Typ & Wortproblem & Definition & Bsp & Maschinenmodell \\ + + Typ 0 & + semi-entscheidbar & + \makecell{$G = (\Sigma, V, S, R)$ \\ $R beliebig$ }& + universelle Sprache & + NTM/DTM akzeptiert L \\ + + Typ 1 & + NP-Schwer & + \makecell{$u \rightarrow v, |u| \leq |v|$ \\ $u \in V^+, S \notin V$ \\ $S \rightarrow \epsilon$ } & + $L = \{ a^ib^ic^i | i \leq 1 \}$ & + \makecell{NTM mit Platzbedarf n \\ erkennt Wörter der Länge n in L \\ $\Rightarrow NTAPE(n)$ } \\ + + Typ 2 & + polynomiell & + \makecell{$A \rightarrow v, A \in V$ \\ $v beliebig$} & + $L = \{ a^ib^i | i \leq 1\}$ & + CYK-Alg. erkennt L in polynom. Zeit, Chomsky-NF, NPDA \\ + + Typ 3 & + linear & + \makecell{$A \rightarrow v, A \in V$ \\ $V \in \epsilon \cup \Sigma \cdot V$} & + $L = \{ a^i | i \leq 1 \}$ & + NEA/DEA erkennt L \\ \end{tabular} -\begin{multicols}{3} - - \subsubsection*{Transitivität} - - $f_1(n) \in \mathcal{O}(f_2(n)) \wedge f_2(n) \in\mathcal{O}(f_3(n))$ \\ - $\Rightarrow f_1(n) \in \mathcal{O}(f_3(n))$ - - \subsubsection*{Summen} - - $f_1(n) \in \mathcal{O}f_3(n)) \wedge f_2(n) \in \mathcal{O}(f_3(n))$ \\ - $\Rightarrow f_1(n) + f_2(n) \in \mathcal{O}(f_3(n))$ - - \subsubsection*{Produkte} - - $f_1(n) \in \mathcal{O}(g_1(n)) \wedge f_2(n) \in \mathcal{O}(g_2(n))$ \\ - $\Rightarrow f_1(n) \cdot f_2(n) \in \mathcal{O}(g_1(n) \cdot g_2(n))$ - - - \columnbreak - - \subsection{Master-Theorem} - - Sei $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ mit $f(n) \in \Theta(n^c)$ und i - $T(1) \in \Theta(1)$. Dann gilt - $ - T(n) \in \begin{cases} - \Theta(n^c) &\text{wenn } a < b^c, \\ - \Theta(n^c \log n) &\text{wenn } a = b^c, \\ - \Theta(n^{\log_b(a)}) &\text{wenn } a > b^c. - \end{cases} - $ - - \subsubsection{Monome} - - \begin{itemize} - \item $a \leq b \Rightarrow n^a \in \mathcal{O}(n^b)$ - \item $n^a \in \Theta(n^b) \Leftrightarrow a = b$ - \item $\sum_{v \in V}deg(v) = \Theta(m)$ - \item $\forall n \in \mathbb{N}: \sum^n_{k=0}k = \frac{n(n+1)}{2}$ - \item $ - \sum^b_{i=a}c^i \in \begin{cases} - \Theta(c^a) &\text{wenn } c < 1, \\ - \Theta(c^b) &\text{wenn } c > 1, \\ - \Theta(b-a) &\text{wenn } c = 1. - \end{cases} - $ - \item $\log(ab) = \log(a) + \log(b)$ - \item $\log(\frac{a}{b}) = \log(a) - \log(b)$ - \item $a^{\log_a(b)} = b$ - \item $a^x = e^{ln(a) \cdot x}$ - \item $\log(a^b) = b \cdot \log(a)$ - \item $\log_b(n) = \frac{\log_a(n)}{\log_a(b)}$ - \end{itemize} - - %\subsubsection{Konstante Faktoren} - % - %$a \cdot f(n) \in \Theta(f(n))$ +\subsection{Automaten} +DEA $A = (Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, s \in Q, F \subseteq Q)$ \\ +NEA $A = (Q, \Sigma, \delta: Q \times (\Sigma \cup \{ \epsilon \} \rightarrow 2^Q, s \in Q, F \subseteq Q)$ +NPDA \\ +DPDA \\ +DTM \\ +NTM \\ +\subsection{Pumping-Lemma} +\begin{multicols}{2} +Erfüllt: +\begin{itemize} + \item["$\exists$"] Wähle $n = 2$ + \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ + \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$ + \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ +\end{itemize} +Widerlegen: +\begin{itemize} + \item["$\exists$"] Wähle $n = 2$ + \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ + \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$ + \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ +\end{itemize} \end{multicols} -\begin{minipage}{0.7\textwidth} - - \section{Sortieren} - - \begin{tabular}[t]{c || c | c | c | c} - Algorithmus & best case & average & worst & Stabilität \\ - \hline - Insertion-Sort & - $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\ - Bubble-Sort & - $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\ - Merge-Sort & - $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & stabil\\ - Quick-Sort & - $\mathcal{O}(n \log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & i.A. nicht stabil\\ - Heap-Sort & - $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & nicht stabil\\ - \hline - Bucket-Sort & - $\Theta(n+m)$ & $\Theta(n+m)$ & $\Theta(n+m)$ & - stabil $e \in [0, m)$\\ - Radix-Sort & - $\Theta(c \cdot n)$ & $\Theta(c\cdot n)$ & $\Theta(c\cdot n)$ & - stabil $e \in [0, n^c)$\\ - \end{tabular} -\end{minipage} -\hfill -\begin{minipage}{0.3\textwidth} - \subsection{Heaps} - - \begin{tabular}[t]{c || c} - Bin.-Heap & Laufzeit \\ - \hline - push(x) & $\mathcal{O}(\log n)$ \\ - popMin() & $\mathcal{O}(\log n)$ \\ - decPrio(x, x') & $\mathcal{O}(\log n)$ \\ - build([$\mathbb{N}$; n]) & $\mathcal{O}(n)$ - \end{tabular} - - \begin{itemize} - \item linkes Kind: $2v + 1$ - \item rechts Kind: $2v + 2$ - \item Elternknoten: $ \lfloor \frac{v - 1}{2} \rfloor $ - \end{itemize} - -\end{minipage} - - \begin{multicols}{2} +Potenzmengenkonstuktion NEA $\rightarrow$ DEA + +\begin{tabular}{c | c | c} + Zustand & a & b \\ + \hline + $\{\underline{s}\}$ & $\{s, q_1\}$ & $\{f\}$ \\ + $\{\underline{s}, q_1\}$ & $\{s, q_1\}$ & $\{f, q_2\}$ \\ + $\{f\}$ & $\{f\}$ & $\{f\}$ \\ + $\{f, q_2\}$ & $\{f\}$ & $\{f, q_1, q_2\}$ \\ + $\{f, \underline{s}\}$ & $\{f, s, q_1\}$ & $\{f\}$ \\ + $\{f, \underline{s}, q_1\}$ & $\{f, s, q_1\}$ & $\{f, q_2\}$ \\ +\end{tabular} - \section{Datenstrukturen} - - \subsection{Listen} - - \begin{tabular}{c || c | c | c || c} - Operation & DLL & SLL & Array & Erklärung(*) \\ - \hline - first & 1 & 1 & 1 & \\ - last & 1 & 1 & 1 & \\ - insert & 1 & 1* & n & nur insertAfter \\ - remove & 1 & 1* & n & nur removeAfter \\ - pushBack & 1 & 1 & 1* & amortisiert \\ - pushFront & 1 & 1 & n & \\ - popBack & 1 & n & 1* & amortisiert \\ - popFront & 1 & 1 & n & \\ - concat & 1 & 1 & n & \\ - splice & 1 & 1 & n \\ - findNext & n & n & n - - \end{tabular} - - \subsection{Hash-Tabelle} - $\mathcal{H}$ heißt \textbf{universell}, wenn für ein zufälliges gewähltes - $h \in \mathcal{H}$ gilt: $U \rightarrow \{0, ..., m-1\}$ \\ - $\forall k, l \in U, k \neq l: Pr[h(k) = h(l)] = \frac{1}{m}$ \\ - $h_{a,b}(k) = ((a\cdot k + b) \mod p) \mod m$ - - \subsection{Graphen} - - \begin{tabular}{c || c} - Algorithmus & Laufzeit \\ - \hline - BFS/DFS & $\Theta(n+m)$\\ - topoSort & $\Theta(n)$\\ - Kruskal & $\Theta(m \log n)$\\ - Prim & $\Theta((n+m)\log n)$ \\ - Dijksta & $\Theta((n + m) \log n)$\\ - Bellmann-Ford & $\Theta(nm)$\\ - Floyd-Warshall & $\Theta(n^3)$ \\ - \end{tabular} - +\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] + + \node[state,initial,accepting] (S) {$S$}; + \node[state] (q_1) [right of=S] {$q_1$}; + \node[state] (q_2) [right of=q_1] {$q_2$}; + \node[state] (f) [below of=q_1] {$f$}; + + \path[->] + (S) edge [loop above] node {a} () + (S) edge node [below] {a} (q_1) + (S) edge node [left] {b} (f) + (q_1) edge [bend right] node [above] {a} (S) + (q_1) edge node [below] {b} (q_2) + (q_2) edge [bend right] node [above] {b} (q_1) + (q_2) edge [loop right] node {b} () + (q_2) edge node {a} (f) + (f) edge [loop left] node {a,b} () + ; + +\end{tikzpicture} \end{multicols} -\newpage - \begin{multicols}{2} +Entfernen von $\epsilon$-Übergängen + +\begin{tabular}{c | c | c} + Zustand & a & b \\ + \hline + $S$ & $q_1$ & $S, q_1, q_2, q_3$ \\ + $q_1$ & $q_2, q_3$ & $q_3$ \\ + $q_2$ & $q_1$ & $S, q_2, q_3$ \\ + $q_3$ & $q_1$ & $S, q_2, q_3$ \\ +\end{tabular} - \subsubsection{DFS} - - \begin{tabular}{c || c | c} - Kante & DFS & FIN \\ - \hline - Vorkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\ - Rückkante & groß $\rightarrow$ klein & klein $\rightarrow$ groß \\ - Querkante & groß $\rightarrow$ klein & groß $\rightarrow$ klein \\ - Baumkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\ - \end{tabular} - \subsection{Bäume} - \subsubsection{Heap} - Priorität eines Knotens $\geq (\leq)$ Priorität der Kinder. - \textbf{BubbleUp}, \textbf{SinkDown}. \textbf{Build} mit \textbf{sinkDown} - beginnend mit letztem Knoten der vorletzten Ebene weiter nach oben. - \textbf{decPrio} entweder updaten, Eigenschaft wiederherstellen; löschen, - mit neuer Prio einfügen oder Lazy Evaluation. - - \subsubsection{(ab)-Baum} - Balanciert. \textbf{find}, \textbf{insert}, \textbf{remove} in - $\Theta(log n)$. Zu wenig Kinder: \textbf{rebalance} / \textbf{fuse}. - Zu viele Kinder: \textbf{split}. - - Linker Teilbaum $\leq$ Schlüssel k $<$ rechter Teilbaum +\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] + + \node[state,initial] (S) {$S$}; + \node[state,accepting] (q_1) [right of=S] {$q_1$}; + \node[state,accepting] (q_2) [below of=q_1] {$q_2$}; + \node[state] (q_3) [below of=S] {$q_3$}; + + \path[->] + (S) edge node {b} (q_1) + (S) edge node [above left] {$\epsilon$} (q_2) + (q_1) edge node {a} (q_2) + (q_1) edge [bend left] node [above right] {b} (q_3) + (q_2) edge node {\epsilon} (q_3) + (q_3) edge node [below left] {a} (q_1) + (q_3) edge node {b} (S) + (q_3) edge [loop left] node {b} () + ; + +\end{tikzpicture} +\end{multicols} - Unendlich-Trick, für Invarianten. +Minimierung von Automaten +\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] + + \node[state,initial] (S) {$S$}; + \node[state] (p) [right of=S] {$p$}; + \node[state] (q) [right of=p] {$q$}; + \node[state] (t) [below of=p] {$t$}; + \node[state,accepting] (r) [below of=q] {$r$}; + \node[state] (v) [below of=t] {$v$}; + \node[state] (u) [below of=r] {$u$}; + + \path[->] + (S) edge [loop above] node {0} () + (S) edge node {1} (p) + (p) edge [loop above] node {1} () + (p) edge node {0} (q) + (q) edge [bend left] node {0} (S) + (q) edge node {1} (r) + (t) edge node [right] {0} (S) + (t) edge [bend right] node {1} (r) + (r) edge [bend right] node [above] {0} (t) + (r) edge node {1} (u) + (v) edge node {0} (S) + (v) edge node[left] {1} (r) + (u) edge node {0} (v) + (u) edge [loop right] node {1} () + ; + +\end{tikzpicture} + +\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] + + \node[state,initial] (S) {$[S]$}; + \node[state] (p) [right of=S] {$[p]$}; + \node[state] (q) [right of=p] {$[q]$}; + \node[state,accepting] (r) [right of=q] {$[r]$}; + + \path[->] + (S) edge [loop above] node {0} () + (S) edge node {1} (p) + (p) edge [loop above] node {1} (p) + (p) edge node {0} (q) + (q) edge[bend left] node {0} (S) + (q) edge node {1} (r) + (r) edge[bend right] node [above] {1} (p) + ; + +\end{tikzpicture} + + + +\begin{tikzpicture} [binary tree layout] + \node[align=center] (1) {s,p,q,r,t,a,v \\ $\epsilon$ trennt} + child { + node {r} + } + child { node[align=center] {s,p,q,t,u,v \\ 1 trennt} + child { node[align=center] {s,p,u \\ 0 trennt} + child { node {s} } + child { node {p,u} } + } + child{ + node {q,t,v} + } + }; +\end{tikzpicture} - \subsection{Union-Find} - Rang: höhe des Baums, damit ist die Höhe h mind. $2^h$ Knoten, h $\in - \mathcal{O}(\log n)$. - Union hängt niedrigen Baum an höherrängigen Baum. Pfadkompression hängt alle - Knoten bei einem \textbf{find} an die Wurzel. +\subsection{Nerode-Relation} +\subsection{Chomsky-NF} - \columnbreak - \section{Amortisierte Analyse} +\section{NP-Vollständigkeit} - \subsection{Aggregation} - Summiere die Kosten für alle Operationen. Teile Gesamtkkosten durch Anzahl - Operationen. +\section{Kellerautomaten} - \subsection{Charging} - Verteile Kosten-Tokens von teuren zu günstigen Operationen (Charging). Zeige: - jede Operation hat am Ende nur wenige Tokens. +\subsection{$4COLOR \in NP$} - \subsection{Konto} - Günstige Operationen bezahlen mehr als sie tatsächlich kosten (ins Konto - einzahlen). Teure Operationen bezahlen tatsächliche Kosten zum Teil mit - Guthaben aus dem Konto. \textbf{Beachte: Konto darf nie negativ sein!} +\subsection{$3COLOR \propto 4COLOR$} - \subsection{Potential (Umgekehrte Kontomethode)} - Definiere Kontostand abhängig vom Zustand der Datenstruktur - (Potentialfunktion) +\subsubsection{Transformation} +\subsubsection{Äquivalenz/Korrektheit} - amortisierten Kosten = tatsächliche Kosten - $+ \Phi(S_\text{nach}) -\Phi(S_\text{vor})$ +\section{Approximationsalgorithmen} -\end{multicols} +\section{Huffman-Kodierung} -\section{Pseudocode} -\scriptsize -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - DFS(Graph G, Node v) \\ - mark v \\ - dfs[v] := dfsCounter++ \\ - low[v] := dfs[v] \\ - \For{u $\in$ N(v)}{ - \eIf{not marked u}{ - dist[u] := dist[v] + 1 \\ - par[u] := v \\ - DFS(G, u) \\ - low[v] := min(low[v], low[u]) \\ - }{low[v] := min(low[v], dfs[u])} - } - fin[v] := fin++ \\ - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - topoSort(Graph G) \\ - fin := [$\infty$; n] \\ - curr := 0 \\ - \For{Node v in V}{ - \If{v is colored}{DFS(G,v)} - } - return V sorted by decreasing fin \\ - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - Kruskal(Graph G) \\ - U := Union-Find(G.v) \\ - PriorityQueue Q := empty \\ - \For{Edge e in E}{Q.push(e, len(e))} - \While{Q $\neq \emptyset$}{ - e := Q.popMin() \\ - \If{U.find(v) $\neq$ U.find(u)}{ - L.add(e) \\ - U.union(v, u) \\ - } - } - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - Prim(Graph G) \\ - Priority Queue Q := empty \\ - p := [0; n] \\ - \For{Node v in V}{ - Q.push(v, $\infty$) \\ - } - \While{Q $\neq \emptyset$}{ - u := Q.popMin() \\ - \For{Node v in N(u)}{ - \If{v $\in$ Q $\wedge$ (len(u, v) $<$ Q.prio(v))}{ - p[v] = u \\ - Q.decPrio(v, len(u, v) \\ - } - } - } - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - BFS(Graph G, Start s, Goal z) \\ - Queue Q := empty queue \\ - Q.push(s) \\ - s.layer = 0 \\ - \While{Q $\neq \emptyset$}{ - u := Q.pop() \\ - \For{Node v in N(u)}{ - \If{v.layer = $-\infty$}{ - Q.push(v) \\ - v.layer = u.layer + 1 - } - \If{v = z}{ - return z.layer - } - } - } - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - Dijkstra(Graph G, Node s) \\ - d := [$\infty$; n] \\ - d[s] := 0 \\ - PriorityQueue Q := empty priority queue \\ - \For{Node v in V}{ - Q.push(v, d[v]) - } - \While{Q $\neq \emptyset$}{ - u := Q.popMin() \\ - \For{Node v in N(u)}{ - \If{d[v] $>$ d[u] + len(u, v)}{ - d[v] := d[u] + len(u, v) \\ - Q.decPrio(v, d[v]) \\ - } - } - } - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - BellManFord(Graph G, Node s) \\ - d := [$\infty$, n] \\ - d[s] := 0 \\ - \For{n-1 iterations}{ - \For{(u, v) $\in$ E}{ - \If{d[v] $>$ d[u] + len(u, v)}{ - d[v] := d[u] + len(u, v) - } - } - } - \For{(u, v) $\in$ E}{ - \If{d[v] $>$ d[u] + len(u, v)}{ - return negative cycle - } - } - return d - \end{algorithm} -\end{minipage} -\begin{minipage}{.25\linewidth} - \begin{algorithm}[H] - FloydWarshall(Graph G) \\ - D := [$\infty$, n $\times$ n] \\ - \For{(u, v) $\in$ E}{D[u][v] := len(u, v)} - \For{v $\in$ V}{D[v][v] := 0} - \For{i $\in 1,...,n$}{ - \For{(u,v) $\in V \times V$}{ - D[u][v] := min(D[u][v], D[u][$v_i$] + D[$v_i$][v]) \\ - } - } - return D - \end{algorithm} -\end{minipage} \end{document} |