1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
\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}
|
