The Gateway to Computer Science Excellence
+3 votes

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 by Veteran (57.2k points) | 345 views
yes it would be false

2 Answers

+12 votes
Best answer

Check the figure !!

by Veteran (50.9k points)
selected by
Thank you @kapil for providing a very clean expalnation.
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.

by Active (1.2k points)

Related questions

+1 vote
3 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,918 users