Problem $1.$ Given a digraph G $=($V$,$ A$)$:

$($a$)$ formulate the problem of finding the shortest path from a node s in V to all other

nodes in V as an MCNF problem.

$($b$)$ discuss how to identify the shortest paths from s to each of the other nodes from

the solution of the LP you proposed in $($a$).$

$($c$)$ what is the smallest possible valid value of uij that you could use in this formulation,

and why?