Minimum Spanning Tree Algorithm Question

[tonokio]

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?

 

[Default User]

I wasn't sure if this was the best place to post since there isn't
really an algorithm section for programming.

It's not. The newsgroup comp.programming is a likely candidate,
possibly sci.math.

If you have trouble converting your algorithm to code, then this is
right place, probably.




Brian

 

[Alan Johnson]

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.