S1 is True. Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination
of the weights. All path weights are linear combinations of edge weights, so the
relative order of path weights is preserved. This means that a shortest path in G
will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to
kilometer, the shortest paths don't change.
S2 is false. consider the following counter-example. Let a graph contain only the following 2 paths-: S-W-T and S-A-B-T. Let the weights of the edges be -: S-W:2 W-T:2 S-A:1 A-B:1 B-T:1
Now the shortest path between S-T is S-A-B-T. Now add a weight of 5 (c=5) to all edges, and convince yourself the new shortest path will be S-W-T.
An airline charges a fixed price for each direct flight. For each sequence of hopping flights,
the ticket price is the sum of the fares of the individual sectors.
TripGuru has precalculated the cheapest
routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its
website.
Overnight, the government has added a 13% luxury service surcharge to the cost of each. Which of the
following describes the impact of this surcharge on TripGuru's computation?
A
There is no impact. Cheapest routes between all pairs of cities remains unchanged.
B
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any
cheapest route where there is a shorter route in terms of number of flights.
C
The surcharge favours hopping flights with more sectors. TripGuru should recompute any
cheapest route where there is a longer route in terms of number of flights.
D
The impact is unpredictable. TripGuru should recompute all cheapest routes.
Second way of asking the question on shortest path when we multiply constant with all edge's weight. Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination
of the weights. All path weights are linear combinations of edge weights, so the
relative order of path weights is preserved. This means that a shortest path in G
will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to
kilometer, the shortest paths don't change.
An airline charges a fixed price for each direct flight. For each sequence of hopping flights,
the ticket price is the sum of the fares of the individual sectors.
TripGuru has precalculated the cheapest routes between all pairs of cities on this airline's route network
so that it can offer an optimum choice instantly to customers visiting its website.
The airline has decided to become a full-service carrier and has included a meal on each sector. To
account for this, the airline has added a flat "convenience fee" of Rs 300 on each sector.
Which of the
following describes the impact of this surcharge on TripGuru's computation?
A
There is no impact. Cheapest routes between all pairs of cities remains unchanged.
B
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any
cheapest route where there is a shorter route in terms of number of flights.
C
The surcharge favours hopping flights with more sectors. TripGuru should recompute any
cheapest route where there is a longer route in terms of number of flights.
D
The impact is unpredictable. TripGuru should recompute all cheapest routes.
The cost per edge increases, so the price for a path with n hops increases by 300n. This means that a
shorter path incurs a smaller penalty, so a longer "shortest" path in the original graph may be superseded
by a shorter one after adding the penalty on each edge.
Accepted Answers:
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route
where there is a shorter route in terms of number of flights.
Consider a graph G. Let T be a BFS tree with root r. Let d(u,v) denote the length of the
shortest path between the nodes u and v.
If v is visited before u in the breadth first search traversal, which of the following
statements is true ?
A
d(r,v) > d(r,u)
B
d(r,v) = d(r,u)
C
d(r,v) < d(r,u)
D
insufficient information to comment on d(r,v) and d(r,u)
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?