Algorithm

Given a directed graph with non-negative edge weights, suppose we have computed the shortest paths from a given source to all the other vertices. If we modify the graph in such a way that the weights of all the edges are doubled, then, the shortest paths remain the same and only the total weights of the paths change. 1.True 2.False solution: a) True The given statement is true. Given a weighted graph with non negative edges, and a shortest path from source to all the other vertex, if we double the weight of the edges, the shortest path remains same, only total path weight changes. It is because weight of all path gets multiplied by same amount. Here the number of edges in a path doesn't matter, as just the weight is replaced on each path at fixed ratio.