Question $2$:$30$ points

You are given a weighted, directed graph $G=(V,E)$ with all edge weights being positive

integers. Answer the following questions accordingly.

$($a$)[10$ points$]$ Assume that the shortest path $P$ between nodes $s$ and $t$ on $G$ is already cal$-$

culated, where the set of edges that constitute $P$ and the total weight of shortest path $k$

is also given to you.

Assume that a new graph $G_1=(V,E^{\text{'}})$ is generated by modifying $G,$ where vertices and

edges are the same, but the weight of each edge is incremented by $2.$ Would $P$ still

be the shortest path between $s$ and $t$ over the new graph $G_1?$ How would the weight of

shortest path $k$ could change over the new graph, if at all?

$($b$)$ points