MST with shortest path optimisation

Consider we want to build McMaster Maps, the best online route planning tool in existence. The developers of McMaster maps have decided to represent road information in terms of a a massive graph in which nodes are crossing and the edges are the roads between crossings. The developers of McMaster Maps will be optimised toward computing the directions to McMaster University is the only destination that matters. Hence, McMaster Maps will be optimised toward computing the directions to McMaster University. To do so, McMaster Maps maintains single-sink shortest path index that maintains the shortest path from any node to McMaster University. This index is represented by the typical path and cost arrays as computed by either Dijkstra or Bellman-Ford. Once in a while, an update to the road network happens: The weight of a single edge changes (this can represent adding and removing edges: addition changes the weight of the edge from $\infty$ to a numeric value and removing changes the weight of the edge from a numeric value to $\infty$)

P1.1

Given the road network as a graph $\mathcal{G}$, the shortest path index, and the edge that was changes, write an algorithm that determines whether the shortest path index is still valid. You may assume the graph is already updated. Argue why your algorithm is correct. What is the complexity of your algorithm?

The shortest path index is invalid in two cases:

• If the new shortest path from $u$ via edge $(u,v)$ is shorter than the current shortest path from $v$ to the destination. This is checked by the condition $cost[u] + w < cost[v]$.
• If $v$‘s current shortest path to the destination goes through $u$ and the new weight $w$ makes this path longer than $v$ current shortest path cost. This is checked by $cost[u] + w > cost[v]$. If both of these conditions met, shortest path index remains valid.

Therefore the algorithm is correct $\square$

The algorithm performs a constant number of comparison and array lookups. Thus it is $O(1)$

P1.2

Assume the shortest path index is no longer valid: provide a modification of Dijkstra algorithm that restores the index to a valid state without recomputing all shortest paths. You may assume the graph is already updated. Argue why your algorithm is correct.

Correctness: Let $T$ be the shortest path tree rooted at the sink vertex $t$ before the edge update, and let $T'$ be the tree true shortest path tree after the edge update. We define a following boundary function:

or $B(i)$ is the set of vertices whose true shortest path to $t$ is at most $i$ and strictly less than their distance in $T$. The following invariant will hold of the while loop:

For base case, $i=0$, $B(0)$ is empty, thus invariant holds

Suppose the invariant holds for $k$, that is at $k$-th iteration $B(k)$ and invariant holds. Let $x$ be the vertex extracted from $Q$ in the $k+1$-th iteration. We argue that $x \in B(k+1) \setminus B(k)$, or $\text{dist}_{T'}(x,t)=k \space \land \space \text{dist}_{T'}(x,t) < \text{dist}_{T}(x,t)$

First, note that $x$ must have been inserted into $Q$ by some previous iteration, say when visiting a vertex $y \in B(j)$ for some $j < i$. By the induction hypothesis, $\text{cost}[y] = \text{dist}_{T'}(y,t)$ at that time, so the tentative distance $\text{cost}[y] + w(y,x)$ used to insert $x$ into $Q$ equals $\text{dist}_{T'}(x,t)$. Since $x$ is extracted in the $k+1$-th iteration, we have $\text{dist}_{T'}(x,t) = k+1$. Moreover, we must have $\text{dist}_{T'}(x,t) < \text{dist}_{T}(x,t)$, for otherwise $x$ would have been visited before via a shorter path in $T$, contradicting the fact that $\text{dist}_{T'}(x,t) = i$. Thus, $x \in B(k+1) \setminus B(k)$. The algorithm then correctly updates $\text{cost}[x]$ to $\text{dist}_{T'}(x,t)$ and $\text{path}[x]$ to its parent $y$ in $T'$. Furthermore, for each neighbor $z$ of $x$, if $\text{cost}[x] + w(x,z) < \text{cost}[z]$, then the path to $z$ through $x$ is shorter than its current path, so the algorithm correctly updates $\text{cost}[z]$ and $\text{path}[z]$ and inserts $z$ into $Q$ with the updated distance.

Therefore, after the $k+1$-th iteration, the invariant holds for all vertices in $B(k+1)$, including the newly added vertex $x$ and possibly some of its neighbors. By induction, the invariant holds for all $i$. $\square$

P1.3

Explain which graph representation you used for your algorithm and what the complexity of your modified-Dijkstra algorithm is using this graph representation.

note: Express the complexity in terms of the number of nodes affected by the change. For example, use a notation in which $C$ is the number of nodes affected by the edge change, $\text{incoming}(C)$ the incoming edges of $C$, and $\text{outgoing}(C)$ the outgoing edges of $C$.

The algorithm use an adjacency list representation, as each vertex maintains a list of its outgoing edges.

The overall complexity is $O((|\text{outgoing}(C)| |C|)\log |C|)$

The main loop run until $Q$ is empty. Per iteration, it extracts the vertex $x$ with minimum distance from $Q$, which takes $O(\log|C|)$ time, where $|C|$ is the number of affected vertices.

For each outgoing edge $(x,y)$ of $x$, update the distance and parent of $y$ and either decrease its keep in $Q$ or insert into $Q$. The operation takes $O(\log|C|)$ time worst-case.

The total number of iterations of the inner loop is bounded by $|\text{outgoing}(C)|$ as each outgoing edge of an affected vertex is processed at most once.

Space complexity is $O(|C|)$, as min-priority queue $Q$ stores at most one entry per affected vertex.

P1.4

What is the worst-case complexity of your solution if you use the other graph representation?

If an adjacency matrix representation is used, the graph is represented by a $|V|\times|V|$ matrix, where $|V|$ is the number of vertices in the graph.

With this representation, the main difference in the algorithm is in the loop that iterates over the neighbors of the current vertex $x$. In an adjacency matrix, finding the neighbors of $x$ requires scanning the entire row corresponding to $x$ in the matrix, which takes $O(|V|)$ time. Therefore, the overall time complexity of the modified Dijkstra’s algorithm using an adjacency matrix becomes:

If all vertices are affected ($|C| = |V|$), the complexity becomes $O(|V|^2 \log |V|)$.

Space complexity is $O(|V|^2)$, as the matrix requires storing $|V|^2$ entries.