dijkstra

Question

Which of the following statements is/are True?

I.Consider a weighted directed graph G and let ‘P’ be a shortest path from u to v for u,v∈V. If we double the weight of every edge in the graph for each ‘e’ belongs to E, then P will still be a shortest path from u to v.
II.The time complexity to detect negative weight cycles in an arbitrary directed graph is O(V+E).

Comments

I is true and II is false ??

Answer 1

consider their are two paths exist between u and v
1st path is u-a-b-v having cost x+y+z

2nd path is u-c-v having cost p+q

now shortest path is 1st path that means x+y+z $\leq$ p+q
now even if we multiply this inequivality by 2 it will not change 2x+2y+2z $\leq$ 2p+2q

Bellmon-ford Algorithm is used to detect the negative weight cycle in graph but its time complexity is O(|V||E|)
PS: even Karp's algorithms have time complexity of O(|V||E|)

I. TRUE
II. FALSE