$(10$ points$)$ Let $G=(V,E)$ be a weighted, directed graph. Assume

that $G$ is initialized using Initialize$-$Single$-$Source $(G,s).$ Prove

that if a sequence of relaxation steps ever sets $s.$ to a non$-$NiL value,

then $G$ contains a negative weight cycle.

$(20$ points$)$ Consider the graph $G$ :

Use Bellman$-$Ford to find the single source shortest path graph

starting at vertex $s.$ Please process the edges in the following order:

$(s,a),(a,b),(a,c),(s,c),(d,a),(d,c),(b,d),(e,d),(e,b),(b,f),(f,e),(c,g),$

$(g,d),(g,h),(d,h),(h,e),(i,h),(e,i),(f,i).$ Draw the subgraph show$-$

ing shortest path from $s$ to all the other vertices.

Please draw when necessary