All Pairs Shortest Paths and Matrix multiplication

Here, an "All pairs shortest paths" algorithm, that runs in $O(|V|^3log|V|)$ time is presented.

Pseudo-Code:


      EXTEND-SHORTEST-PATH$(L,W)$

1. $n = L.row$
2. $L'$ is a new $n \times n$ matrix
3. for $i$ from 1 to $n$
4.       for $j$ from 1 to $n$
5.             $l_{ij}' = \infty$
6.             for $k$ from 1 to $n$
7.                   $l_{ij}' = min(l_{ij}',l_{ik}+w_{kj})$
8. return L'

Explanation:

Here we assume that each matrix object has it's rows saved in it as an attribute as $row$. We basically try every path from $i$(source vertex) through $k$ (intermediate vertex) to $j$ (destination vertex).
This algorithm runs in $O(n^3)$ time.

NOTE: This algorithm is similar to Matrix multiplication.

Here $L$ is actually $L^{m-1}$ for some $m$, and $L'$ is $L^m$. We don't use $m$ in the algorithm to remove any dependence on $m$.

EXTEND-SHORTEST-PATH is used by:

      SLOW-ALL-PAIRS-SHORTEST-PATHS$(W)$

1. $n = W.rows$
2. $L^{(1)} = W$
3. for $m=2$ to $n-1$
4.       let $L^{(m)}$ be a new $n \times n$ matrix
5.       $L^{(m)} =$EXTEND-SHORTEST-PATHS$(L^{(m-1)},W)$
6. return $L^{(n-1)}$

And this will run in $O(n^4)$ time.

This can be reduced by seeing the fact that just like matrix multiplication, EXTEND-SHORTEST-PATH is also associative. Thus $\text{EXTEND-SHORTEST-PATH}(L^{(3)},W) = \text{EXTEND-SHORTEST-PATH}(L^{(2)},L^{(2)})$.

Therefore, we can just do repeated squaring. That is, squaring until we get a $L^{m}$, where $m \geq n-1$. We know that $\delta(i,j) = l_{ij}^{n-1} = l_{ij}^n=l_{ij}^{n+1}=...$ because the maximum number of edges in the shortest path between two vertices is $|V|-1 = n-1$. Since $l_{ij}$ denotes the minimum weight of any path between $i$ and $j$, that contains at most $m$ edges.

Thus:

      FAST-ALL-PAIRS-SHORTEST-PATHS$(W)$

1. $n=W.rows$
2. $L^{(1)} = W$
3. $m=1$
4. while $m< n-1$
5.       let $L^{(2m)}$ be a new $n \times n$ matrix
6.       $L^{(2m)}=$EXTEND-SHORTEST-PATHS$(L^{(m)},L^{(m)})$
7.       $m=2m$
8. return $L^{(m)}$

This obviously runs in $O(n^3logn)$ time. Cool!

About Dijkstra's Algorithm to find the Single source shortest paths

Pseudo-Code:

      DIJKSTRA$(G,s,w)$

1. INITIALIZE-SINGLE-SOURCE$(G,s)$
2. $S = \phi$
3. $Q = G.V$
4. while  $Q \neq \phi$
5.       $u = $EXTRACT-MIN$(Q)$
6.       $S = S \cup {u}$
7.       for vertex $v \in G.adj[u]$
8.             RELAX$(u,v,w)$

Explanation:

Here, $S$ is a set, which keeps track of the vertices whose final shortest weight path from the source vertex $s$ has been determined. $Q = G.V-S$. In the while loop, we extract the vertex from the priority queue $Q$, which has the minimum estimated distance from the source vertex $s$. Then this vertex $u$ is added to $S$, and all the edges connected to it are RELAXed. 

Dijkstra's algorithm is a greedy algorithm, as it always takes the vertex, not in $S$, which has the minimum distance from the source vertex $s$. 

Why does it work?

Basically, we try to prove that the following loop invariant is correct:

At the start of each iteration of the while loop in line-4, all the vertices in $S$ have their final shortest weight path determined. That is for all $v \in S, v.d = \delta(s,v)$.

Now, 

Initialization: Trivial. Since, $S = \phi$ initially.

Maintenance: See the figure given above (taken directly from CLRS). Here $s$ is the source vertex, $x$ is in $S$, that is the last vertex in $S$ that is in the path from $s$ to $u$. And, $y$ is the first vertex in the path that is not int $S$. 

Now, assume that $u.d \neq \delta(s,u)$, that is, $u.d$ is not equal to the minimum path weight, even after $u$ is added to $S$. Therefore, we try to get a contradiction here.

Now, when $x$ was added to $S$, then $x.d = \delta(s,x)$, and using the convergence property (which is stated below), we can say that $y.d = \delta(s,y)$.

Convergence Property:

If $s \to...\to u \to v$ is a shortest path in $G$ for some $u,v \in V$, and if $u.d = \delta(s,u)$ at any time prior to relaxing edge $(u,v)$, then $v.d = \delta(s,v)$ at all times afterwards.

Now, note that $y$ will be extracted after $u$. Because of that, at the time of extraction of $u$, $u.d \leq y.d$. Now since we have non-negative weights, thus $$\delta(s,y) \leq \delta(s,u)$$. And we know that $$y.d = \delta(s,y) \\ \leq \delta(s,u) \\ \leq u.d$$
The last step was taken due to the upper-bound property:

We always have $v.d \geq \delta(s,v)$ for all vertices $v \in V$, and once$v.d$ achieves the value $\delta(s,v)$, it never changes.

But since $y$ is extracted later than $u$, therefore $u.d \leq y.d$, but we've $u.d \geq y.d$ according the analysis above. So, because of that, we can say that $u.d = y.d$. So $y.d = \delta(s,y) = \delta(s,u) = u.d$, as all the inequalities change to equalities, since the first and last elements of the inequalities are equal. This would mean that $u.d = \delta(s,u)$, which is a contradiction.

Thus the loop invariant exists here too.

Termination: Easy. As the maintenance makes sure that every vertex inside $S$ has the right path weight (and parent), therefore in the end, when $Q = \phi$ and $S = G.V$, we'll have the loop invariant satisfied.

Therefore, we can say that Dijkstra's algorithm works correctly. Cool!

Running time:

Note that we extract one vertex only once, and we have a total of $|V|$ vertices inside $Q$. Therefore, the outer while loop works $|V|$ times. And since one vertex is extracted only once, therefore, it's adjacency list is traversed only once, leading to the fact that the total number of time the inner  for loop works $|E|$ times. (Since there are a total of $|E|$ edges in total, obviously)

There are three priority queue operations here, INSERT( line 3), DECREASE-KEY (implicit in RELAX) and EXTRACT-MIN.
Therefore we can say that the total running time of the algorithm is: $$ O(|V|\times\text{(INSERT)}+|V|\times\text{(EXTRACT-MIN)}+|E|\times\text{DECREASE-KEY})$$

There are three possible implementations of the priority queue :

1. Array implementation: If we have every vertex numbered from 1 to $|V|$, then we can implement $Q$ using an array of length $|V|$. Then INSERT and DECREASE-KEY can be done in $O(1)$ time, and EXTRACT-MIN in $O(|V|)$ time. Therefore, a total of $O(|V|+|V|^2+|E|) = O(|V|^2)$ time is taken.
2. Min-heap implementation: Here BUILD-HEAP will take a total of $O(|V|)$ time, DECREASE-KEY and EXTRACT-KEY both will take $O(lg\text{ }|V|)$ time. Therefore, we have a total running time of $O((|E|+|V|)lg \text{ }|V|) = O(|E|lg\text{ }|V|)$ time.
3. Fibonacci Heaps: Here, the DECREASE-KEY can be implemented in $O(1)$  time. Thus a total running time of $O(|E|+|V|lg |V|)$.

About Bellman-Ford Algorithm for the single-source shortest paths

Pseudo-Code:
      BELLMAN-FORD$(G,w,s)$

1. INITIALIZE-SINGLE-SOURCE$(G,s)$
2. for $i=1$ to $|G.V|-1$
3.       for each edge $(u,v)$ in $G.E$
4.             RELAX$(u,v,w)$
5. for each edge $(u,v)$ in $G.E$
6.       if $v.d >u.d+w(u,v)$
7.             return FALSE
8. return TRUE 

Explanation:

      INITIALIZE-SINGLE-SOURCE$(G,s)$

1. for vertex $v$ in $G.V$
2.       $v.d = \infty$
3.       $v.\pi = NIL$
4.  $s.d = 0$

And,

      RELAX$(u,v,w)$

1. if $v.d>u.d+w(u,v)$
2.      $v.d = u.d+w(u,v)$
3.       $v.\pi = u$

Here, $w$ is the weight function, $G$ is the graph, and has $V$ as it's vertices, and $E$ as it's edges.

Now, the BELLMAN-FORD algorithm can be divided into two parts:

1. Lines 2-4: Makes the predecessor graph. Basically it would compute the needed distances, if the graph doesn't contain any negative-weight cycles.
2. Lines 5-8: Checks whether the graph has a negative-weight cycle or not.

Lines 2-4:

What we're doing here: $|V|-1$ times relaxing all the edges.

Why does it work?
Path relaxation property:

If $p = <v_0,v_1,...,v_k>$ is the shortest path from $s=v_0$ to $v_k$, and we relax the edges of $p$ in the order $(v_0,v_1),(v_1,v_2),...,(v_{k-1},v_k)$, then $v_k.d=\delta(s,v_k)$. This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.

So, basically, even if we add some other relaxations in between this order of relaxations, then too we'll have the same shortest path from $v_0$ to $v_k$.

Here, we're sure that in the first iteration we'll relax $(v_0,v_1)$, regardless of the order of relaxation. Then in the second iteration, we'll relax $(v_1,v_2)$ for sure. Thus in the end, the order is followed, and we get the shortest path from $v_0$ to $v_k$.

So, in the end, we'll get the right path to all the connected vertices.
   
Lines 5-7:

This part is used to check whether there is some negative-weighted cycle in $G$.

This is done via checking $v.d >u.d + w(u,v)$. If it's TRUE, then we've a cycle, and we return a FALSE. Otherwise, it's okay, and we return a TRUE.

The point of doing this comparison:
Well, assume that we've a negative-weight cycle $c = <v_0,v_1,...v_k>$ in $G$, but BELLMAN-FORD still returns a TRUE value. Now, that would mean that $$v.d \leq u.d+ w(u,v)\text{ (line 6's inverse)} $$
Now, doing this for all the vertices of the cycle:
$$\sum_{i=1}^{k}v_i.d \leq \sum_{i=1}^{k}v_{i-1}.d + \sum_{i=1}^{k}w(v_{i-1},v_i) $$

But, since $v_0=v_k$ for a cycle, $\sum_{i=1}^{k}v_i.d = \sum_{i=1}^{k}v_{i-1}.d$. Because of which we get $$0 \leq \sum_{i=1}^{k}w(v_{i-1},v_i)$$ which is contradictory, since $c$ is a negative weight cycle.
This is the reason why this comparison works.

Running time:
Due to lines 2-4, the running time obviously goes to $O(|V||E|)$.

About Prim's algorithm

And yeah, you guessed it right, I've studied the Prim's algorithm too, and am gonna talk trash 'bout it. Biatch. I mean it's cool since it's my fucking blog, I can say anything. Cool. Cool cool cool.

Coming back to the topic.
How does the Prim's algorithm satisfy the generic MST method ?:

Well, the set $A$ basically contains a subset of the final MST built. We can say that $A$ respects a cut, $(S,V-S)$, in which set $S$ contains all the vertices that are joined via the edges in $A$. Prim's algorithm finds a light edge that crosses  this cut, and by corollary 23.2, we can say that this light edge is safe.

Pseudo-code:

     MST-PRIM$(G,w,r)$

1. for each $u \in G.V$
2.       $u.key = \infty $
3.       $u.\pi = NIL$
4. $r.key = 0 $
5. $Q = G.V$
6. while $Q \neq \phi$
7.       $u =$ EXTRACT-MIN$(Q)$ 
8.       for each $v \in G.Adj[u]$
9.             if $v \in Q$ and $w(u,v)<v.key$
10.                   $v.\pi = u$
11.                   $v.key = w(u,v)$

Explanation:

Basically, we have this tree, living inside $A$ (thriving...etc.). We have this min-priority queue $Q$ which has all the vertices that are not in the set of vertices joined by the edges in $A$. Each vertex maintains the distance from the tree built. Therefore initially it's $\infty$ for all vertices, but the root. Now, we keep on adding those vertices to the tree that are the nearest to it (using the EXTRACT-MIN operation), until no vertex is left, ( that is, $Q$ becomes empty).

Implementation:

The priority queue is implemented using min-heaps. If we use Fibonacci heaps, we can get a better running time.

Running time:

EXTRACT-MIN runs in $O(lg V)$.
Updating keys in the priority queue takes $O(lg V)$  in min-heap , and $O(1)$ time in a fibonacci heaps. (that is, the DECREASE-KEY operation)

The while loop runs in $O(E)$ time and the inner loop in a total of $O(E)$ time. Thus a total of $O(E lgV+VlgV) = O(ElgV)$ time, if we use min-heaps, and $O(E+VlgV)$ time if we use fibonacci heaps.

About Kruskal's algorithm

So, I read the Kruskal algorithm from CLRS, and guess what? there are a lotta things to be remembered!

So, the implementation (pseudo code) of this algorithm is something like:
      MST-KRUSKAL($G$,$w$)

1.  $A = \phi$
2. for each vertex $v \in G.V$
3.       MAKE-SET($v$)
4. sort the edges of $G.E$ into nondecreasing order by weight $w$
5. for each edge $(u,v) \in G.E$, taken in nondecreasing order by weight
6.       if  FIND-SET($u$) $\neq$ FIND-SET($v$)
7.             $A = A \cup \{(u,v)\}$
8.             UNION$(u,v)$
9. return $A$ 

Implementation of sets is done via disjoint-set forests (section 21.3), which use union-by-rank and path-compression optimizations, to get a total running time of $O(m \alpha(n))$ where, $m$ is the total number of MAKE-SET, FIND-SET and UNION operations, and $n$ are the total MAKE-SET operations (which, obviously are always less than $m$).

Now, Kruskal algorithm basically connects two components of the graph $G$, via a light edge. This light edge is obviously safe to add, by using the corollary 23.2. So, initially there are $|V|$ trees, and at the end of the Algorithm, there is just one tree left, connecting all the vertices.

A word about the running time:

• Sorting in line 4 takes $O(E log E)$ time
• Since there are $|V|$ MAKE-SET operations ($n = |V|$), and $m = |V|+|E|$(not considering the constants multiplied to $|E|$), therefore running time comes out to be $$(|V|+|E|)\alpha(|V|)\\ = |E| \alpha(|V|)$$
• So, the total running time is $$O(|E|log|E|+|E|\alpha(|V|)) \\= O(|E|log|E|)$$

CLRS 23.1-11 Decrease the weight of an edge

[CLRS 23.1-11] Given a graph $G$ and a minimum spanning tree $T$, suppose that we decrease the
weight of one of the edges not in $T$. Give an algorithm for finding the minimum
spanning tree in the modified graph.

Well, this one is dependent upon 23.1-5 , which states that there is always an MST that doesn't include the maximum weight edge of a cycle of a graph. Now, let's add the edge whose weight was decreased (say $E_0$) to $T$. This will, obviously make a cycle. Now, we check for the maximum weight edge in the graph thus formed, and remove it (it might be $E_0$ too). The tree thus formed is the MST of the graph.

CLRS 23.1-8 List of sorted edges remains the same

[CLRS 23.1-8]: Let $T$ be a minimum spanning tree of a graph $G$, and let $L$ be the sorted list of the edge weights of $T$. Show that for any other minimum spanning tree $T'$ of $G$, the list $L$ is also the sorted list of edge weights of $T'$ .

Note that $w(T) = w(T')$.

Well, assume that the sorted list of edges for $T'$ is $L'$, which is different from $L$. Then there will be atleast one edge that is excluded (say edge $a$), and an another edge (say $b$) is added to $L'$. Each edge connects one vertex. So we'll have a vertex, (say $\alpha$) which was connected via $a$ in $T$, but in $T'$, it's connected via $b$. If $w(a) = w(b)$, then $L' =L$, so there's no problem. But if the $w(a) \neq w(b)$, then we would have $w(T) \neq w(T')$, which is contradictory. This could only be solved by:

Assume that $w(a) > w(b)$, then we'll have another edge $c$ in $T$, that is replaced by $d$ in $T'$. Moreover, $w(c) < w(d)$, so that $w(a)+w(c) = w(b)+w(d)$, because of which $w(T) = w(T')$. But if that was always possible, then we'll simply take $b$ instead of $a$, and $c$ instead of $d$, thus reducing the total weight, contradicting the fact that $T$, and $T'$ are MSTs.


Therefore, $L$ must be equal to $L'$. Cool. Super cool.

[CLRS 23.1-6] Unique Light edges lead to a unique spanning tree

23.1-6 [CLRS]:Show that a graph has a unique minimum spanning tree if, for every cut of the
graph, there is a unique light edge crossing the cut. Show that the converse is not
true by giving a counterexample.

Here, let's use the theorem 23-1, according to which we can select $A$ to be a subset of $E$, the set of edges that is included in some minimum spanning tree. Then,
Hypothesis-1 : We can always make $A$ such that it can respect any cut $(S,V-S)$.
Eventually, that is very easy to do. We can just ignore all the edges that lie on the cut (that is, connect the two components produced by the cut), and put the rest of the edges into $A$. This leads to an $A$ that respects the underlying cut.

Now, according to the question, each cut corresponds to a light edge. Now we know that we have a total of $2^{n-1}-1$ possible cuts for $n$ vertices. So, each of these cuts, points towards an edge, that, according to the theorem is safe to add into $A$. So we add all the corresponding edges of all the possible cuts.

Hypothesis-2: $|A|=|V|-1$, when $A$ is made by adding all the corresponding light edges of every possible cut.
Let's assume that we'll have $|A|=|V|$. Since there are $|V|$ vertices in total, we're sure to have a cycle in $G_A$. Now, when we make cuts such that we have one vertex of the cycle in one cut, and all the other vertices in the other one, then we'll always leave one edge of the cycle out. Thus, contradicting the assumption. Therefore the hypothesis is true.

Now, we know that $A$ has exactly $|V|-1$ edges in it. Moreover, $A$ will always come to be the same set, on the same graph $G$.

And, we know that a set of $|V|-1$ different edges, for $|V|$ vertices, always leads to an MST.

CONVERSE:
The converse states that, "If a graph has a unique MST, then for every cut of the graph, there is a unique light edge crossing the cut."

[Photo credits : https://github.com/gzc/CLRS/blob/master/C23-Minimum-Spanning-Trees/23.1.md]

[CLRS-23.1-2] Proving the conjecture wrong

23.1-2 Professor Sabatier conjectures the following converse of theorem 23.1. Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree $G$, let $(S,V-S)$  be any cut of $G$ that respects $A$  and let, $(u,v)$ be a safe edge for $A$ crossing $(S,V-S)$. Then, $(u,v)$ is a light edge for the cut. Show that the professor's conjecture is incorrect by giving a counterexample.

So, the basic problem that I faced here was :

Every edge is added to $A$ only after comparing all the other edges that connect both the components of $G_A$. So, $(u,v)$ connecting any two components must be a light edge.

Well, this is obviously wrong. Since, the two components that we're talking about, in both the scenarios are different. That is to say, when we added $(u,v)$ to $A$, there might not be any other edge connecting the two components (like for example, if both the components contain only one vertex), but when we have our present $A$,then we might have many other edges other than $(u,v)$, which connect the chosen components. So, in that case $w(u,y)$ is not necessarily the minimum of all the edges' weights connecting those components.
For example see:

Here, we have a tree (which itself is a graph), let $A$ have all the edges (that is $A$ is the MST here)  $S = \{A,E,D\}$ and $V-S = \{B,C\}$. Now see that $(A,B)$ is not a light edge, even though it is a part of $A$, and is safe.

Proof- Safe edges in a Graph

Consider the following theorem:(23.1 in CLRS)

Let $G =  (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S,V - S)$ be any cut of $ G$ that respects $A$, and let $(u,v)$
be a light edge crossing $(S,V- S)$. Then, edge $(u,v)$ is safe
for $A$.

Now, from what I understood after reading the book, we take an edge $(u,v)$ (that is not in $A$), that is either in $T$ or not. If it is in $T$, then it is already safe. But if it isn't, we can see that since $T$ must include all the vertices of the graph $G$, then there must be some edge $(x,y)$ crossing the cut. (Since $(u,v)$ isn't in $T$). Now, if we make another tree $T'$ that contains $(u,v)$, but not $(x,y)$, then we'll still have an MST, since $(u,v)$ is a light edge, thus $w(u,v) \leq w(x,y)$, therefore, $$w(T') = w(T) - w(x,y)+w(u,v) \\ \leq w(T)$$. Thus $T'$ is an MST of $G$ that contains $(u,v)$. Thus all-in-all, $(u,v)$ is a safe edge. Cool!