search
Log In
3 votes
723 views

Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F

in Algorithms 723 views
0
false.
0
yes it would be false

2 Answers

12 votes
 
Best answer

Check the figure !!


selected by
1
Thank you @kapil for providing a very clean expalnation.
1
nice explanation!!!
0 votes

Absolutely False.....

Think in the terms of number of edges involved in the path.....More the number of edges higher the increase in the path. So definitely  it is possible that some other path with less number of edges became the shortest path.

Related questions

1 vote
0 answers
2
220 views
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.
asked Jul 31, 2018 in Algorithms Rishav Kumar Singh 220 views
1 vote
1 answer
3
345 views
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the shortest ... iii) We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.
asked Dec 13, 2017 in Algorithms VIKAS TIWARI 345 views
1 vote
3 answers
4
397 views
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?
asked Jun 26, 2017 in Algorithms Abhisek Saha 397 views
...