menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

shortest path

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.

edited by
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.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

1 vote
0 answers
2
220 views
shortest path algo
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.
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
shortest path
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 ... We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.
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
Shortest Path Algorithms
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 ?
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
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...