$(30$ points$)$ Recall the problem of single$-$source shortest path $($SSSP$)$ with general edge lengths. Consider a directed graph $G=(V,E)$ and lengths $l_{uv}$inR for edges $(u,v)inE.$ The total length of any cycle $C$ is non$-$negative, i$.$e$.,({\displaystyle \underset{(u)}{\overset{?}{}}},vinC{l}_{uv}0.$ Further consider a source vertex $sinV.$ We want to find the shortest distances from $s$ to other vertices in the graph; you may assume that all vertices are reachable from $s.$

The Bellman$-$Ford algorithm solves this problem in polynomial time. We will re$-$examine this question through the lens of LP$.$

$($a$)(15$ points$)$ Let variables $d_v$ denote the shortest distances from $s$ to vertices vinV. Consider the basic update step of Bellman$-$Ford. Can you rephrase the logic behind the basic update step as linear inequalities for these variables?

$($b$)(15$ points$)$ Can you further design an objective function such that solving the LP $($with the constraints in part $($a$))$ gives the shortest distance from $s$ to a vertex $v?$ Argue for the correctness of your approach.