\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{5-4}{Dan Ports}{No collab}{Recitation \#8}

\paragraph{Algorithm}
Given a graph $G = (V, E)$ and a source node $s$, we will identify the upwards and downwards critical edges by computing for each node the nodes that can be predecessors in a shortest path. We will show (in the proof of correctness below) that an edge is downwards critical if it appears in the shortest-path-predecessor list for the edge's destination vertex, and that it is upwards critical if it is the only shortest-path-predecessor for the destination vertex.
\paragraph{}
We can find the predecessor nodes by modifying Dijkstra's algorithm. Rather than maintaining a single predecessor pointer $\pi[v]$ for every vertex $v \in V$, we maintain a predecessor list that contains a pointer to each node that could be a predecessor in a shortest path to $v$. To do this, we modify the Relax procedure slightly.
If $d[v] > d[u] + w(u,v)$, then in addition to updating the distance $d[v]$ as Dijkstra's algorithm normally does, we also replace $v$'s predecessor list with $u$: $\pi[v] \leftarrow \{u\}$. 
We also check whether $d[v] = d[u] + w(u,v)$. In this case, we append $u$ to $v$'s predecessor list: $\pi[v] \leftarrow \pi[v] \cup \{u\}$. If $d[v] <= d[u] + w(u,v)$, we still do nothing.
\paragraph{}
Once our modified Dijkstra's algorithm terminates, we use the predecessor lists to identify which edges are upwards and downwards critical edges. We iterate through every edge $e \in E$, and let $v$ be the destination vertex of $e$. We check whether $e \in \pi[v]$; if so, then we designate $e$ as downwards-critical if $w(e) > 0$.  We also check whether $e$ is the only element in $\pi[v]$ and designate $e$ as upwards-critical if so.
\paragraph{Runtime analysis}
Our modifications to Dijkstra's algorithm do not affect the runtime. Appending to and/or replacing the list $\pi[v]$ adds only a constant amount of time to each call to Relax. So, if we implement Dijkstra's algorithm using a binary min-heap, it can run in time $O(\abs{E} \lg \abs{V})$. Scanning the predecessor lists requires $\Theta(\abs{E})$ time for loop overhead and to find the lists $\pi[v]$, since we iterate over each $e \in E$. Checking whether each edge $e$ is in its appropriate $\pi[v]$ requires $\Theta(\abs{\pi[v]})$ time, for the appropriate $v$, so the amortized cost of all the tests is $\Theta(\sum_{v\in V}{\abs{\pi[v]}}) = \Theta(\abs{E})$ since there are $\abs{E}$ edges and each one appears in only one set $\pi[v]$ since it only has one destination vertex. So the total cost of the algorithm is $O(\abs{E} \lg \abs{V})$
\paragraph{Proof of correctness}
We will first show that the algorithm correctly generates the list of predecessor nodes. We base this on the correctness of Dijkstra's algorithm, which we can assume since the graph contains no negative weights. First, we show that every element $u \in \pi[v]$ is in fact a shortest-path-predecessor of $v$. Note that, when Relax($u,v,w$) is called, $u$ will only be added to $\pi[v]$ if the cost of the path through $u$ to $v$ is less than that of all previously discovered paths. If a path through some other node $x$ is later discovered that is shorter, then Relax($x,v,w$) will replace $\pi[v]$ with $\{x\}$, removing $u$. By the time the algorithm examines the adjacency list of $v$, it will have found the correct shortest path to $v$, and so it will have called Relax on every shorter path, so every element in $\pi[v]$ is a predecessor node.
\paragraph{}
We next show that there are no predecessor nodes that are not in $\pi[v]$. Suppose there were some $u$ that should be in $\pi[v]$ but is not. This would require that the distance of the shortest path to $u$ is less than the shortest path distance to $v$ by $w(u,v)$, and there can not be any shorter path to $v$. But this would mean that Dijkstra's algorithm would visit $u$ before it visits $v$, and when it calls Relax($u,v,w$), it would find that $d[v]$ is either greater than or equal to $d[u] + w(u,v)$, and add $u$ to $\pi[v]$. So there is no way $u \notin \pi[v]$. Thus, we have shown that $\pi[v]$ contains all shortest-path predecessor nodes of $v$.
\paragraph{}
To show the algorithm is correct, we show that an edge $e$ is downwards critical if and only if it appears in its destination node's predecessor list (and $e$'s weight is non-zero), and that $e$ is upwards critical if and only if it is the only predecessor node of it's destination node. Consider an edge $e$ such that $w(e) > 0$ and call its source node $u$ and its destination node $v$. If $e$ is a shortest-path-predecessor of $v$, then no other path from $s$ to $v$ has length less than the path $s \rightarrow u \rightarrow v$ has length. So if we lower $w(e)$, then we lower the distance of the shortest path to $v$, and so $e$ is downwards-critical. If $e$ is not a predecessor of $v$, then it is not downwards-critical. If it were, then lowering the weight of $e$ would lower the distance of the path to some node $p$. Since $e$ is an edge from $u$ to $v$, this means that the path $s \rightarrow u \rightarrow v \rightarrow p$ would be shortened. This means the path $s \rightarrow u \rightarrow v$ must be the shortest path to $v$ (and so $e \in \pi[v]$), because otherwise there would be a shorter path from $s$ to $v$ and thus a shorter path $s \rightarrow v \rightarrow p$.
\paragraph{}
Next we show that $e$ is upwards-critical if and only if it is the only predecessor of $v$. If $e$ is the only predecessor of $v$, then $s \rightarrow u \rightarrow v$ is shorter than all other paths to $v$, so increasing $w(e)$ increases the shortest distance to $v$. If $e$ is not a predecessor, then there is some shorter path from $s$ to $v$ which does not include $e$, and it will continue to be shorter if $w(e)$ is raised. If $e$ is not the only predecessor, then there is some path from $s$ to $v$ that does not include $e$ that has the same length as the one that includes $e$. The former path will not increase in length if $w(e)$ is raised, so the shortest path from $s$ to $v$ is unchanged. Thus the shortest path to any vertex beyond $v$ is not increased unless $e$ is the only predecessor of $v$.
\paragraph{}
Since we have shown that our algorithm correctly computes the predecessors of each node, and that the predecessors of each node correctly give the upwards and downwards critical edges, our algorithm gives the correct result.



\end{document}