With this set of problems, we will develop algorithms for All$-$Pairs Shortest Paths $($APSP$)$ in graphs. PROBLEM: $($APSP$).$ Given a graph G $=($V$,$E$)$ with w : E $$ R that gives a real weight to every edge.

Find the shortest path from every vertex to every $$other$$ vertex.

The graph could be directed or undirected but we assume it to be a simple graph $($no multiple edges and no self$-$loops$),$ without any negative cycles. Let $|$V $|=$ n and $|$E$|=$ m$.$ Denote by A the weighted adjacency matrix of G$,$ i$.$e$.$

$0$

A$($u$,$v$)=$ wij $=$ w$(($i$,$j$))$

if u $=$ v

if $($u$,$v$)$ in E if $($u$,$ v$)$ in $/$ E

Definition. For u$,$ v in V $,$ let d$($u$,$ v$)$ be the total weight of a shortest path from u to v$.$

In case v is not reachable from u$,$ then d$($u$,$v$)=$ and d$($u$,$u$)=0$ for all u$.$ This information can be visualized as a matrix $($called the distance matrix$)$ D$.$ We will focus on computing the pairwise distance only, but the solutions that we develop can easily be extended to find the actual shortest paths too.

APSP has many applications including all scenarios that we discussed for SSSP $($Single Source Shortest Path$).$

Such a distance matrix is also input for agglomerative or hierarchical clustering.

Suppose the graph is input in the adjacency lists representation.

Problem $1.$ Briefly describe a solution for APSP problem using the Dijkstra$$s algorithm. Discuss when can this solution be adopted?

Problem $4.$ Argue that the goal of APSP problem is to find Ln$1($u$,$ v$)$ for all u and v$,$ if there are no negative cycles in G$.$

Problem $8.$ Prove that the recurrence in $(1)$ is equivalent to

$$

$$min Lh$1($u$,$ v$),$ min

Lh$($u$,$v$)=$

$0$

if h $=0$ and u $=$ if h $=0$ and u $=$

ifh$1$

$1$k$$n

$$min Lh$1($u$,$k$)+$wkv

$1$k$$n

As we discussed that our goal is to compute Ln$1($u$,$v$)$ for all u and v$.$ We can implement recurrence $(2)$ in a straightforward manner, but there will be redundant functions calls $($try to picture this$).$ Therefore, we compute the matrix Ln$1($u$,$ v$)$ in a bottom$-$up manner but first computing the L$0$ matrix, then the L$1$ matrix and so on$.$

Problem $11.$ Recall the following algorithm for multiplying two square matrices Algorithm Algorithm to Compute Z $=$ X $$ Y

$1$: $2$: $3$: $4$: $5$:

$6$:

Z $$ zeros$($n $$ n$)$ fori$=1$tondo

for j $=1$ to n do for k $=1$ to n do

Z$[$i$][$j$]$ Z$[$i$][$j$]+$ X$[$i$][$k$]$ Y $[$k$][$j$]$ return Zh

$$ Initialize the matrix with all entries as $0$

Which operation would have to be redefined and how so as the Lh computation becomes matrix multiplication?

Problem $16.$ Give an O$($n$3$ log n$)$ algorithm to compute the matrix Ln$1$ using repeated squaring. Note that

Algorithm $1$ computes Lh $=$ Lh$1$ A$.$ Assume that n $=2$t for t in Z$+.$

Problem $17.$ Give an efficient algorithm to determine if the graph has a negative cycle.

Problem $24.$ Show that for k $>0,$

v

$|\{$z $\}$

in V k$=\{$v$1,$v$2,...,$vk$\}$ Figure $1$: Subpaths

$($Opt$-$Val$($u$,$ v$,$ k $1)$

Opt$-$Val$($u$,$ k$,$ k $1)+$ Opt$-$Val$($k$,$ v$,$ k $1)$

if vk in $/$ Opt$-$Path$($u$,$ v$,$ k$)$ if vk in Opt$-$Path$($u$,$ v$,$ k$)$

Opt$-$Val$($u$,$ v$,$ k$)=$ min

Problem $25.$ For any u and v describe Opt$-$Path$($u$,$ v$,0)$ and find Opt$-$Val$($u$,$ v$,0).$

From the above problems, we get the following dynamic programming formulation.

$($wuv if k $=0$ Opt$-$Val$($u$,$v$,$k$)=$ minnOpt$-$Val$($u$,$v$,$k$1),$Opt$-$Val$($u$,$k$,$k$1)+$Opt$-$Val$($k$,$v$,$k$1)$o ifk$1(3)$

Problem $26.$ Suppose we are only interesting in finding the distances d$($u$,$ v$)$ for all pairs u and v$.$ State our goal in terms of the Opt$-$Val$($u$,$ v$,),$ i$.$e$.$ for what value of k should we evaluate Opt$-$Val$($u$,$ v$,$ k$).$

Problem $27.$ Give an algorithm to compute Opt$-$Val$($u$,$v$,$n$)$ for all u and v in a bottom$-$up fashion.

You should be able to remove the need of using n matrices, only two will suffice just as above. Also you

should be able to construct the actual shortest paths by backtracking from the value of the shortest paths.

Problem $28.$ What is the runtime of the above algorithm?