Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:

$$ \begin{array}{ll} T[0][k]=T[k][0]=1 & \text { for } k=0,1,2, \ldots, n \\ T[i][j]=2 T[i-1][j]+3 T[i][j-1] & \text { for } 1 \leq i, j \leq n \end{array} $$

Consider the following two algorithms to compute entries of $T$. Assume that for both the algorithms, for all $0 \leq i, j \leq n, T[i][j]$ has been initialized to 1 .

Algorithm $B_k, k \in\{1,2\}$ is said to be correct if and only if it calculates the correct values of $T[i][j]$, for all $0 \leq i, j \leq n$, (as per the recursive formulation) at the end of the execution of the algorithm $B_k$.

Which one of the following statements is true?

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let $s \in V$ be a vertex in $G$. For every $u \in V$ and for every $k \geq 0$, let $d_k(u)$ denote the weight of a shortest path (in terms of weight) from $s$ to $u$ of length at most $k$. If there is no path from $s$ to $u$ of length at most $k$, then $d_k(u)=\infty$.

Consider the statements:

S1: For every $k \geq 0$ and $u \in V, d_{k+1}(u) \leq d_k(u)$.

S2: For every $(u, v) \in E$, if $(u, v)$ is part of a shortest path (in terms of weight) from $s$ to $v$, then for every $k \geq 0, d_k(u) \leq d_k(v)$.

Which one of the following options is correct?

Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.

$$A[i][j] = \left\{ {\matrix{ {1,} & {1 \le j \le i \le 5} \cr {0,} & {otherwise} \cr } } \right.$$

A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r $$\in$$ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is _____________.

Consider the following directed graph: 

Which of the following is/are correct about the graph?