(Solved): 1. Let G=(V,E,w) be a weighted graph. (a) Give an example to show that if the weight of the edges ca ...

1. Let

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.

. Let

be a weighted graph. Define

be the edge with minimum weight among all edges incident at

. Let

. Assume that the weights of the edges are all distinct. Show that there is a minimum spanning tree

of

which contains all the edges in

. 3. Given a directed graph

with weighted edges, along with a specific node

and a tree

. Give an algorithm that checks whether

is a shortest-path tree for

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.8 using a data structure that provides the operations described in Section 6.5.1. In addition to the shortest distance, your algorithm should also output the shortest path.