Question: Consider a Directed Acyclic Graph $($DAG$)$ with nQuestion: Let there is an directed graph with $5$ nodes with the following edges means $x$ is

connected to $y,$ and $z$ is the associated cost$)$: $1-3(6),1-4(3),2-1(3),3-4(2),4-3(1),4-2(1),5-2(4),5-4(2).$

Now, consider $5$ as the source node, and

I. Apply Bellman$-$Ford algorithm to find the single source shortest path. You need to show the

adjacency matrix each time you relax an edge. Relax the edges in this sequence: $1-3,1-4,2-1,3-$

$4,4-3,4-2,5-2,5-4.$ Finally, mention the maximum number of iterations you need to find the

shortest path of all nodes from the source node.

II$.$ Apply Dijkastra algorithm to find the single source shortest path. You need to show the

adjacency matrix each time you relax an edge.

III. Which algorithm will not work if any of the edges is negative? Why it will not work? How the

other algorithm will handle this issue?

number of nodes. The nodes are numbered from $0$ to $(n-1).$ Write

a program that returns a list, which contains all the nodes in

ascending order. Here, list$[$i$]$ contains all ancestors in ascending

order, for the $i^t$ node, and $0i(n-1).$ A node $u$ is an ancestor

of another node $v$ if $u$ can reach v via a set of edges. For example,

consider the following graph. The Output for this graph should be:

$\left[\begin{array}{ccccc}?& ?& ?& ?& ?\\ ?& ?& ?& ?& ?\\ ?& ?& ?& ?& ?\\ 0& 1& ?& ?& ?\\ 0& 2& ?& ?& ?\\ 0& 1& 3& ?& ?\\ 0& 1& 2& 3& 4\\ 0& 1& 2& 3& ?\end{array}\right]$

Explanation:

Nodes $0,1,$ and $2$ do not have any

ancestors.

Node $3$ has two ancestors $0$ and $1.$

Node $7$ has four ancestors $0,1,2$ and $3.$

Special instructions:

$.$ Test your code for these following graphs. Finally, attach a screenshot from your output

console$/$terminal$.$