tonokio wrote:
I wasn't sure if this was the best place to post since there isn't
really an algorithm section for programming. I was curious that if
you're given a MST tree of G and P is the shortest path between two
nodes s and t. If we increaset the cost of each edge of G by some
amount x, would P still be the shortest path between s and t, because
all the values are incremented by x amount or would it change?
Off topic for comp.lang.c++. Setting follow-ups to comp.theory.
To answer your question, the shortest path can change. When you
increment all edges by x, the cost of any particular path increases by
m*x, where m is the number of edges.
So, just for example, let's say you have an s-t path p_1 with 3 edges,
each of cost 1, and another s-t path p_2 with 1 edge of cost 4.
C(p_1)=3, C(p_2)=4. Now, increment every edge by 1. Now, C(p_1)=6,
C(p_2)=5. Notice that p_1 was original cheaper, but after incrementing
is more expensive.
--
Alan Johnson