$1.$ Let $G=(V,E,w)$ be a weighted graph.

$($a$)$ Give an example to show that if the weight of the edges can be

negative, then Dijkstra's algorithm will not be able to compute

correct distances.

$($b$)$ Can we first add a constant value to the weight of each edge to

make all weights non$-$negative, then run the Dijkstra's algorithm

to compute shortest paths? Justify your answer.

$2.$ Let $G=(V,E,w)$ be a weighted graph. Define $(v)$ be the edge with

minimum weight among all edges incident at $v.$ Let $E_{}={?}_{\text{v}\text{i}\text{n}\text{V}}(v).$

Assume that the weights of the edges are all distinct. Show that there

is a minimum spanning tree $T$ of $G$ which contains all the edges in $E_{}.$

$3.$ Given a directed graph $G=(V,E)$ with weighted edges, along

with a specific node $sinV$ and a tree $T=(V,E^{\text{'}}),E^{\text{'}}$subeE. Give an

algorithm that checks whether $T$ is a shortest$-$path tree for $G$ with

starting point s$.$ Your algorithm should run in linear time.

$4.$ Rewrite Dijkstra's algorithm to solve the shortest path problem in

weighted graphs shown in Figure $6\mathrm{.}8$ using a data structure that

provides the operations described in Section $6\mathrm{.}5\mathrm{.}1.$ In addition to the

shortest distance, your algorithm should also output the shortest path.