Home /
Expert Answers /
Computer Science /
1-let-g-v-e-w-be-a-weighted-graph-a-give-an-example-to-show-that-if-the-weight-of-the-edges-ca-pa838

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

`\alpha (v)`

be the edge with minimum weight among all edges incident at

`v`

. Let

`E_(\alpha )=\cup _(vinV)\alpha (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_(\alpha )`

. 3. Given a directed graph

`G=(V,E)`

with weighted edges, along with a specific node

`sinV`

and a tree

`T=(V,E^(')),E^(')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.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.