\documentclass[10pt,a4paper]{article} \usepackage[margin=2cm]{geometry} \usepackage{multicol} \let\assignment5 \usepackage{enumitem} \setenumerate[1]{label=\assignment.\arabic*.} \setenumerate[2]{label=\textit{\alph*})} % textcomp package is not available everywhere, and we only need the Copyright symbol % taken from http://tex.stackexchange.com/a/1677/23992 \DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}} \usepackage{fancyhdr} \renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{0pt} \fancyhead{} \fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps} \pagestyle{fancy} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} \usepackage{tikz} \usepackage{array} \usepackage{caption} \usepackage[hidelinks]{hyperref} \usepackage{url} \parindent0pt \title{Algoritmen en Datastructuren - assignment \assignment} \author{Camil Staps\\\small{s4498062}} \begin{document} \maketitle \thispagestyle{fancy} \begin{multicols}{2} \begin{enumerate} \item See table \ref{tab:dijkstra}. \begin{minipage}{\linewidth} \centering \scriptsize \begin{tabular}{r *{8}{| >{$}c<{$}}} Relaxing & A & B & C & D & E & F & G & H \\\hline -- & 0 & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ A & 0 & 5 & \infty & \infty & 4 & \infty & \infty & \infty \\ E & 0 & 5 & \infty & \infty & 4 & 15 & \infty & \infty \\ B & 0 & 5 & 11 & \infty & 4 & 15 & 15 & \infty \\ C & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 28 \\ D & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ F & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ G & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \\ H & 0 & 5 & 11 & 12 & 4 & 15 & 15 & 24 \end{tabular} \captionof{table}{Running Dijkstra's algorithm} \label{tab:dijkstra} \end{minipage} \item See table \ref{tab:bellmanford}\footnote{NB: in the slides that were given to us I couldn't find the use of $\pi$ as a variable. I'm assuming $\pi[v]$ means the parent (predecessor) of $v$, as in \url{http://web.cs.ucdavis.edu/~bai/ECS122A/ShortPathAlgs.pdf}.}. We see that after three passes we cannot relax any edge any more. Therefore, there does not exist a negative-weight cycle. \begin{minipage}{\linewidth} \centering \scriptsize \begin{tabular}{r *{5}{| >{$}c<{$}}} Pass & s & t & x & y & z \\\hline 0 & (\infty, \bot) & (\infty, \bot) & (\infty, \bot) & (\infty, \bot) & (0, \bot) \\ 1 & (2, z) & (8, s) & (7, z) & (9, s) & (0, \bot) \\ 2 & (2, z) & (5, x) & (6, y) & (9, s) & (0, \bot) \\ 3 & (2, z) & (4, x) & (6, y) & (9, s) & (0, \bot) \\ 4 & (2, z) & (4, x) & (6, y) & (9, s) & (0, \bot) \\ \end{tabular} \captionof{table}{Running the Bellman-Ford algorithm} \label{tab:bellmanford} \end{minipage} \item See figure \ref{fig:dijkstra-incorrect}. Dijkstra's algorithm does not take into account negative weights. While Bellman-Ford's algorithm will report the existence of a negative-weight cycle, Dijkstra's algorithm will not do this. It will report distance of $0$ and $1$ for the source vertex and the other vertex, while in fact both vertices have a distance of $-\infty$ from the source. \begin{minipage}{\linewidth} \centering \begin{tikzpicture}[node distance=2cm,->,>=stealth] \node[draw,circle] (A) {A}; \node[draw,circle,right of=A] (B) {B}; \draw (A) edge[bend left] node[above] {-1} (B); \draw (B) edge[bend left] node[below] {-1} (A); \end{tikzpicture} \captionof{figure}{A graph on which Dijkstra's algorithm produces incorrect results} \label{fig:dijkstra-incorrect} \end{minipage} \item In a directed graph with non-negative weights from $\{0,1,\dots,W\}$, we know every edge will at most have weight $W\cdot(|V|-1)$. We can thus use a $W\cdot(|V|-1)$-length array, and at index $i$ store a list of the vertices with maximum distance $i$. At the beginning, the source vertex is at index $0$ and all others are at index $W\cdot(|V|-1)-1$. Then, we iterate over the array starting at index $0$, and for every vertex, say at index $i$ we apply the relaxation step (which means moving vertices from their index $j$ to a lower index $j'\geq i$). Iterating the array takes $\pazocal O(W\cdot|V|)$, and every edge is visited only once, so that takes $\pazocal O(|E|)$. Therefore, this algorithm runs in $\pazocal O(W\cdot|V|+|E|)$. \item We can use Bellman-Ford, where we don't relax every edge $|V|-1$ times, but just $k$ times. We are then sure to have correct distances for the vertices that are at most $k$ edges away from the source vertex. Since Bellman-Ford runs in $\pazocal O(|V|\cdot|E|)$, this will run in $\pazocal O(k\cdot|E|)$. \item First, build a set $$D = \{(x,y,d(x,y)) \mid x,y\in \{s,t\}\cup C\},$$ where $$C=\{u \mid (u,\dots)\in E' \text{ or } (\dots,u)\in E'\}.$$ We then have all distances between $s$ and $u$, $u$ and $v$, $v$ and $t$, $s$ and $v$, $u$ and $t$, and $s$ and $t$. To build $C$ has complexity $\pazocal O(|E'|)$. To build $D$ takes $\pazocal O(|C|^2)\cdot p$, where $p$ is the complexity of the search algorithm you're using to find $d(x,y)$. Next, we let $r:=(\bot,\infty)$ and for every $(u,v) = e' \in E'$ we do $r:=(e',d(s,u) + d(u,v) + d(v,t))$ if $d(s,u)+d(u,v)+d(v,t) < \mathrm{snd}(r)$. We also do $r:=(e',d(s,v) + d(u,v) + d(u,t))$ if $d(s,v)+d(u,v)+d(u,t) < \mathrm{snd}(r)$. For this step we use $D$ (so that we don't calculate the same distance over and over again). This takes $\pazocal O(|E'|)\cdot a_D$, where $a_D$ is the complexity of the access function of $D$. Finally we return $\mathrm{fst}(r)$. \end{enumerate} \end{multicols} \end{document}